LightOJ 1341 Aladdin and the Flying Carpet（唯一分解定理）

http://lightoj.com/volume_showproblem.php?problem=1341

题意：
给你矩形的面积（矩形的边长都是正整数），让你求最小的边大于等于b的矩形的个数。

思路：
根据唯一分解定理，把X写成若干素数相乘的形式，则X的正因数的个数为：（1+a1）（1+a2）（1+a3）...（1+an）。（ai为指数）

因为这道题目是求矩形，所以知道一个正因数后，另一个正因数也就确定了，所以每组正因数重复计算了两遍，需要除以2。

最后减去小于b的因数。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<stack>

 using namespace std;

 const int maxn=1e6+;

 int n;

 int cnt=;

 int primes[maxn];

 int vis[maxn];

 void get_primes()

 {

     int m=sqrt(maxn+0.5);

     for(int i=;i<=m;i++)

     {

         if(!vis[i])

         {

             for(int j=i*i;j<=maxn;j+=i)

                 vis[j]=;

         }

     }

     for(int i=;i<=maxn;i++)

         if(!vis[i])   primes[cnt++]=i;

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     int T;

     int kase=;

     get_primes();

     scanf("%d",&T);

     while(T--)

     {

         long long a,b;

         scanf("%lld%lld",&a,&b);

         long long x=a;

         if(a<=b*b)  {printf("Case %d: 0\n",++kase);continue;}

         long long ans=;

         for(int i=;i<cnt&&primes[i]*primes[i]<=a;i++)

         {

             if(a%primes[i]==)

             {

                 long long num=;

                 while(a%primes[i]==)

                 {

                     num++;

                     a/=primes[i];

                 }

                 ans*=(+num);

             }

         }

         if(a>)  ans*=;

         ans/=;

         for(long long i=;i<b;i++)

             if(x%i==)  ans--;

          printf("Case %d: %lld\n",++kase,ans);

     }

     return ;

 }

巴特西

LightOJ 1341 Aladdin and the Flying Carpet（唯一分解定理）

最新文章

热门文章