2016huasacm暑假集训训练四数论

题目链接：https://vjudge.net/contest/125308#problem/G

题意：求有多少x(1<=x<=n),使得gcd(x,n)>=m; 先求n的所有大于等于m的因子, 刚开始用了模拟，超时，看了下往上的题解，说要用到欧拉函数求解，就看了下欧拉函数， ans=∑phi[n/ei];phi[i]为欧拉函数，为不大于i且与i互质的正整数个数对于一个与ei互质且小于等于n/ei的正整数p来说，p*ei<=n,gcd(p*ei,n)=ei;则phi[n/ei]就是1~n中的与n最大公约数是ei的个数。而n与1~n的最大公约数必定是n的因子。所以符合gcd(x,n)>=m的x为n所有大于等于m因子的倍数，用phi即可避免重复。

那么此题就很容易解了

AC代码:

 #include <stdio.h>

 #define size 1000000

 int a[size];

 int P( int n )

 {

     int ans = n;

     for( int i =  ; i*i <= n ; i++ )

     {

         if( n%i== )

         {

             ans = ans / i * (i-);

             while( n%i== )

                 n /= i;

         }

     }

     if(n>)

         ans = ans / n * (n-);

     return ans;

 }

 int main()

 {

     int t , n , m , t1 , ans;

     scanf("%d",&t);

     while( t-- )

     {

         scanf("%d%d",&n,&m);

         t1 = ans = ;

         for( int i =  ; i*i<=n ; i++ )

         {

             if( n%i ==  )

             {

                 if(i*i==n)

                     a[t1++] = i;

                 else

                 {

                     a[t1++] = i;

                     a[t1++] = n/i;

                 }

             }

         }

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

         {

             if( a[i]>=m )

             {

                 ans += P( n/a[i] );

             }

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

2016huasacm暑假集训训练四数论_B

最新文章

热门文章

巴特西

2016huasacm暑假集训训练四 数论_B

最新文章

热门文章

2016huasacm暑假集训训练四数论_B