lightoj 1341

lightoj 1341  Aladdin and the Flying Carpet

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

题意：给定整数 a， b ，求 区间[b, a] 内的 a 的约数对的个数，a 的约数对（比如[2, 3] 与 [3, 2] 是同一对），也就是说前因子要小于后因子。

思路：我的思路比较直接，就是求 a 的约数的个数(用欧拉函数)，除以 2 就得到约数对数, 然后暴力求解区间 [1, b] 内的 a 的约数。最后两数相减得到结果。

代码：

 #include <iostream>

 #include <stdio.h>

 #include <algorithm>

 #include <queue>

 #include <map>

 #include <set>

 #include <vector>

 #include <cstring>

 #include <math.h>

 using namespace std;

 typedef long long LL;

 const int maxv = ;

 bool nu[maxv];

 int phi[], k;

 void prime()        //素数表

 {

     memset(nu, , sizeof(nu));

     int i, j;

     k = ;

     nu[] = , phi[] = ;

     for(i = ; i < maxv; i += )

     {

         if(!nu[i])    phi[k++] = i;

         for(j = ; j < k && i * phi[j] < maxv; j++)

         {

             nu[i*phi[j]] = ;

             if(!(i % phi[j]))    break;

         }

     }

 }

 LL gain_ans(LL a)        //得到区间[1, a] 的约数对数

 {

     int i = , j;

     LL s = ;

     if(a == )        return ;

     while(phi[i] < a && i < k )    //欧拉函数

     {

         j = ;

         if(a % phi[i] == )

             while(a % phi[i] == )

                 a /= phi[i], j++;

         s *= (j+);

         i++;

     }

     if(a != )    s *= ;

     return s / ;

 }

 int main()

 {

     LL  b, a, s, q;

     int t, cs = ;

     prime();

     freopen("lightoj1341.txt", "r", stdin);

     cin >> t;

     while(t--)

     {

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

         q = ;

         if(b >= sqrt(a))    s = ;        // b 大小限定

         else

         {

             q = ;

             for(int i = ; i < b; ++i)    //暴力枚举 [1, b] 的a 的约数

                 if(a % i == )    q++;

             s = gain_ans(a) - q;

         }

         printf("Case %d: %lld\n", cs++, s);

     }

     return ;

 }