LOJ 1341 Aladdin and the Flying Carpet（质因子分解）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：http://lightoj.com/volume_showproblem.php?problem=1341

题意：给两个数a，b，求满足c * d = a且c>=b且d>=b的c, d二元组对数，(c, d)和(d, c)属于同一种情况。

思路：根据唯一分解定理，先将a唯一分解，则a的所有正约数的个数为num = (1 + a1) * (1 + a2) *...* (1 + ai)，这里的ai是素因子的指数。现在我们知道了a的因子个数为num，假设因子从小到大排列为

X1,X2,...,Xnum 因为是求二元组，所以num先除以2，然后减去那些比b小的因子即可（比b小的一定和比较大的组合，所以不用考虑很大的情况）。

code：

 #include <cstdio>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 int prime[MAXN + ];

 void getPrime()

 {

     memset(prime, , sizeof(prime));

     for (int i = ; i <= MAXN; ++i) {

         if (!prime[i]) prime[++prime[]] = i;

         for (int j = ; j <= prime[] && prime[j] <= MAXN / i; ++j) {

             prime[prime[j] * i] = ;

             if (i % prime[j] == ) break;

         }

     }

 }

 LL factor[][];

 int fatCnt;

 int getFactors(LL x)

 {

     fatCnt = ;

     LL tmp = x;

     for (int i = ; i <= prime[] && prime[i] * prime[i] <= tmp; ++i) {

         factor[fatCnt][] = ;

         if (tmp % prime[i] == ) {

             factor[fatCnt][] = prime[i];

             while (tmp % prime[i] == ) {

                 ++factor[fatCnt][];

                 tmp /= prime[i];

             }

             ++fatCnt;

         }

     }

     if (tmp != ) {

         factor[fatCnt][] = tmp;

         factor[fatCnt++][] = ;

     }

     LL ret = ;

     for (int i = ; i < fatCnt; ++i) {

         ret *= (1L + factor[i][]);

     }

     return ret;

 }

 int main()

 {

     getPrime();

     int nCase;

     scanf("%d", &nCase);

     for (int cnt = ; cnt <= nCase; ++cnt) {

         LL a, b;

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

         if (b * b > a) {

             printf("Case %d: 0\n", cnt);

             continue;

         }

         LL num = getFactors(a);

         num /= ;

         for (int i = ; i < b; ++i) {

             if (a % i == ) --num;

         }

         printf("Case %d: %lld\n", cnt, num);

     }

     return ;

 }