和GCD相关的“个数”及“求和”问题—

和GCD相关的“个数”及“求和”问题——hdu 2588、nyist 1007

本文主要是介绍和GCD相关的“个数”及“求和”问题——hdu 2588、nyist 1007，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

hdu 2588 GCD

http://acm.hdu.edu.cn/showproblem.php?pid=2588

大意：

Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.

分析：已知(a,b)=k --> (a/k, b/k)=1

所以，问题即是求解有多少个x，满足 (n/k, x/k)=1 且k>=m, 1<=x<=n

那么，需要枚举公约数k，然后欧拉函数。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1e5+10;
int prim[N],cnt;
bool vis[N];
void getpri(){for(int i=2;i<N;i++){if(!vis[i]) prim[cnt++]=i;for(int j=0;j<cnt&&prim[j]*i<N;j++){vis[prim[j]*i]=1;if(i%prim[j]==0) break;}}
}
int Euler(int a){if(a==1) return 1;int ans=a;for(int i=0;i<cnt&&prim[i]<=a;i++){if(a%prim[i]==0) {ans=ans-ans/prim[i];while(a%prim[i]==0) a/=prim[i];}}if(a>1) ans=ans-ans/a;return ans;
}
int main()
{getpri();int t;int n,m;cin>>t;while(t--){scanf("%d%d",&n,&m);int len=(int)sqrt(n);int ans=0;for(int i=1;i<=len;i++){if(n%i==0){if(i>=m){ans=ans+Euler(n/i);}if(n/i!=i && n/i>=m){ans=ans+Euler(i);}//cout<<i<<": "<<ans<<endl;}}printf("%d\n",ans);}return 0;
}

nyist 1007 GCD

http://acm.nyist.net/JudgeOnline/problem.php?pid=1007

大意：和hdu 2588 差不多，不过需要求解x的和，而非个数

分析：看这样一个子问题，n=24, k=2, 那么x可以等于

2 ， 10 ，14 ， 22

x全部除以2，即成

1 ， 5 ， 7 ， 11

这刚好是n/k=24/2=12的欧拉函数的成员

他们的和等于多少呢？

1+11=12

5+7=12

12*2=24

也即 $\\ \frac{n}{k}\times 2$
将这个2推广成公式，即 $\\ \frac{1}{2} \phi(\frac{n}{k})$
所以，和n的最大公约数是k的x的和等于 $\\ k \times \frac{n}{k} \frac{1}{2} \phi(\frac{n}{k}) = \frac{n}{2} \phi(\frac{n}{k})$

检测了一下，1——1e6内欧拉函数是奇数的只有1和2

用此公式可以解决n/k=2的情况，但是n=k的情况需要特殊处理。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1e5+10,mod=1000000007;
typedef long long LL;
int prim[N],cnt;
bool vis[N];void getpri(){cnt=0;for(int i=2;i<N;i++){if(!vis[i]) prim[cnt++]=i;for(int j=0;j<cnt&&prim[j]*i<N;j++){vis[prim[j]*i]=1;if(i%prim[j]==0) break;}}
}int Euler(int a){if(a==1) return 1;int ans=a;for(int i=0;i<cnt&&prim[i]<=a;i++){if(a%prim[i]==0) {ans=ans-ans/prim[i];while(a%prim[i]==0) a/=prim[i];}}if(a>1) ans=ans-ans/a;return ans;
}int main()
{getpri();int t;LL n,m;cin>>t;while(t--){scanf("%lld%lld",&n,&m);LL ans=0LL;int len=(int)sqrt(n);for(int i=1;i<=len;i++){if(n%i==0){if(i>=m){if(i==n) ans=(ans+n)%mod;else ans=(ans+n*Euler(n/i)/2)%mod;}if(n/i!=i && n/i>=m) {if(n/i==n) ans=(ans+n)%mod;else ans=(ans+n*Euler(i)/2)%mod;}//cout<<i<<": "<<ans<<endl;}}printf("%lld\n",ans);}return 0;
}

这篇关于和GCD相关的“个数”及“求和”问题——hdu 2588、nyist 1007的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！