首页 > 代码库 > nyoj998(euler)

nyoj998(euler)

题意:题意:给出n和m,求满足条件gcd(x, n)>=m的x的gcd(x, n)的和,其中1<=x<=n,1<= n, m <= 1e9;

思路:此题和nyoj1007差不多,比1007简单一点;
http://www.cnblogs.com/geloutingyu/p/5966998.html(1007题解)


1
#include <iostream> 2 #include <stdio.h> 3 #define ll long long 4 using namespace std; 5 6 /*****此题中这个euler函数会超时 7 int euler(int n){ 8 int ans=1; 9 for(int i=2; i*i<=n; i++){ 10 if(n%i==0){ 11 ans*=(i-1); 12 n/=i; 13 while(n%i==0){ //×××这种写法虽然避免了除法运算,不过需要好多乘法运算可能会超时 14 ans*=i; 15 ans/=i; 16 } 17 } 18 } 19 if(n>1){ 20 ans*=n-1; 21 } 22 }*/ 23 24 int euler(int n){ 25 int ans=n; 26 for(int i=2; i*i<=n; i++){ 27 if(n%i==0){ 28 ans=ans*(i-1)/i; 29 while(n%i==0){ 30 n/=i; 31 } 32 } 33 } 34 if(n>1){ 35 ans=ans*(n-1)/n; 36 } 37 } 38 39 40 int main(void){ 41 ll a, b; 42 while(~scanf("%d%d", &a, &b)){ 43 ll ans=0; 44 for(int i=1; i*i<=a; i++){ 45 if(a%i==0){ 46 if(i>=b){ 47 ans+=(ll)(i*(euler(a/i))); 48 } 49 if(i*i!=a && a/i>=b){ 50 ans+=(ll)(a/i*(euler(i))); 51 } 52 } 53 } 54 printf("%lld\n", ans); 55 } 56 return 0; 57 }

 

nyoj998(euler)