首页 > 代码库 > HDOJ 4983 Goffi and GCD
HDOJ 4983 Goffi and GCD
题意: 给你 N 和 K,问有多少个数对满足 gcd(N-A, N) * gcd(N - B, N) = N^K 分析: 由于 gcd(a, N) <= N,于是 K>2 都是无解,K=2 只有一个解 A=B=N,只要考虑 K = 1 的情况就好了 其实上式和这个是等价的 gcd(A, N) * gcd(B, N) = N^K,我们枚举 gcd(A, N) = g,那么gcd(B, N) = N / g。问题转化为统计满足 gcd(A, N) = g 的 A 的个数。这个答案就是 ?(N/g) 只要枚举 N 的 约数就可以了。答案是 Σ?(N/g)*?(g) g | N 计算 ? 可以递归,也可以直接暴力计算,两个都可以。
Goffi and GCD
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 361 Accepted Submission(s): 118
Problem Description
Goffi is doing his math homework and he finds an equality on his text book: \(\gcd(n - a, n) \times \gcd(n - b, n) = n^k\).
Goffi wants to know the number of (\(a, b\)) satisfy the equality, if \(n\) and \(k\) are given and \(1 \le a, b \le n\).
Note: \(\gcd(a, b)\) means greatest common divisor of \(a\) and \(b\).
Goffi wants to know the number of (\(a, b\)) satisfy the equality, if \(n\) and \(k\) are given and \(1 \le a, b \le n\).
Note: \(\gcd(a, b)\) means greatest common divisor of \(a\) and \(b\).
Input
Input contains multiple test cases (less than 100). For each test case, there‘s one line containing two integers \(n\) and \(k\) (\(1 \le n, k \le 10^9\)).
Output
For each test case, output a single integer indicating the number of (\(a, b\)) modulo \(10^9+7\).
Sample Input
2 1 3 2
Sample Output
2 1HintFor the first case, (2, 1) and (1, 2) satisfy the equality.
Source
BestCoder Round #6
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> using namespace std; const int mod=(1e9+7); long long int euler_phi(int n) { int m=(int)sqrt(n+0.5); long long int ans=n; for(int i=2;i<=m;i++) if(n%i==0) { ans=ans/i*(i-1); while(n%i==0) n/=i; } if(n>1) ans=ans/n*(n-1); return ans; } int n,k; int main() { while(scanf("%d%d",&n,&k)!=EOF) { if(n==1) puts("1"); else if(k>2) puts("0"); else if(k==2) puts("1"); else { long long int ans=0; for(int g=1;g<=n;g++) { if(n<g*g) break; if(n%g==0) { if(g!=n/g) ans=(ans+(euler_phi(n/g)*euler_phi(g))%mod*2)%mod; else ans=(ans+(euler_phi(n/g)*euler_phi(g))%mod)%mod; } } printf("%I64d\n",ans%mod); } } return 0; }
HDOJ 4983 Goffi and GCD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。