GCD nyoj 1007 (欧拉函数+欧几里得)

GCD

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述: The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6.
(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem:
Given integers N and M,please answer sum of X satisfies 1<=X<=N and (X,N)>=M.

输入

The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (1<=N<=10^9, 1<=M<=10^9), representing a test case.

输出

Output the answer mod 1000000007

样例输入

样例输出

1

35

1305000

题意：1<= x <= n ，求gcd(x,n) >= m 说有满足条件的x的和  （最后要模Mod=1000000007)
分析：

如果是求满足条件的x的个数：

因为x要满足1<=x<=n 且gcd(x,n)>=m，所以x为n的因子，即gcd(x,n)=x>=m，设y=n/x，
则y的欧拉函数为小于y且与y互质的数的个数。假设与y互质的数为p1,p2,p3……，那么gcd(x*pi,n)=x>=m.
即要找出所有符合要求的y的欧拉函数值的和即可。

因为1<= x <= n 若gcd(x,n) = x >= m 推出x是n的因子  y = n/x 与y互质且小于y的数pi 总共有eular(y)个
gcd(x*pi,n) = x >= m  所以此时满足条件的x的个数有eular(y)个

又因为 gcd(a,n) = gcd(n-a,n) 【定理记住】 所以此条件下x的和sum = n*eular(y)/2
最后再依此求出n的所有因子 计算sum相加即可

计算x的总和：附上代码

/*

author:谦智

HDU 2588-GCD(欧拉函数)  数论

*/

#include<iostream>

using namespace std;

const int Mod = ;

#define LL long long

LL eular(LL n) ;

LL eularSum(LL k) {

  if (k == ) return ;//特殊值

  return k*eular(k)/;

}

int main() {

  int t;

  cin >> t;

  while (t--) {

    LL n, m;

    cin >> n >> m;

    LL sum = ;

    if (n ==  && m == ) {//特殊情况

      cout <<  << endl;

      continue;

    }

    for (LL i = ; i*i <= n; i++) {

      if (n%i == ) {

        if (i >= m) {

          sum = (sum + n*eular(n/i)/)%Mod; //==》 sum = (sum + i*(n/i)*eular(n/i)/2)%Mod

//          sum = (sum + i*eularSum(n/i))%Mod;//总共有 eular(n/i)个x使得gcd(x,n) >= m

        }

        if (n/i >= m && i*i != n) {

　　　　　　//只需要在这里加一个i== 1的情况上面不要加  不然会重复

          if (i == ) sum = (sum + n)%Mod;//当eular(i) < 2时只需要加上此时唯一满足条件的x即可  其他的eular(i)一定都是偶数因为gcd(a,n)= gcd(n-a,n)

          else sum = (sum + n*eular(i)/)%Mod;

//           sum = (sum + n/i*eularSum(i))%Mod;

        }

      }

    }

    cout << sum << endl;

  }

}

LL eular(LL n) {

  LL ans = n;

  for (LL 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;

}

计算x的个数：附上代码

//计算 x小于n 且gcd(x,n) >= m 的x的个数

#include<iostream>

using namespace std;

int eular(int n) ;

int main() {

  int t;

  cin >> t;

  while (t--) {

    int n, m;

    cin >> n >> m;

    int sum = ;

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

      if (n%i == ) {

        if (i >= m) {

          sum += eular(n/i);

        } else if (n/i >= m && i*i != n) {

          sum += eular(i);

        }

      }

    }

    cout << sum << endl;

  }

}

int eular(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;

}

秒客网

GCD nyoj 1007 (欧拉函数+欧几里得)

GCD

相关文章