首页 > 代码库 > 【HDOJ】4983 Goffi and GCD

【HDOJ】4983 Goffi and GCD

2024-07-19 16:55:21   223人阅读

题意说的非常清楚，即求满足gcd(n-a, n)*gcd(n-b, n) = n^k的(a, b)的不同对数。显然gcd(n-a, n)<=n, gcd(n-b, n)<=n。因此当n不为1时，当k>2时，不存在满足条件的(a,b)。而当k=2时，仅存在(n, n)满足条件。因此仅剩n=1以及k=1需要单独讨论：
当n = 1时，无论k为何值，均有且仅有(1,1)满足条件，此时结果为1；
当k = 1时，即gcd(n-a, n)*gcd(n-b, n) = n，则令gcd(n-a, n) = i，则gcd(n-b, n) = n/i。也即求(n-a)/i与n/i互素且(n-b)/(n/i)与n/(n/i)互素的(a, b)的对数和。

 1 #include <cstdio> 2 #include <cmath> 3  4 const int MOD = (1e9+7); 5  6 __int64 getNotDiv(int x) { 7     int i, r = x; 8     __int64 ret = x; 9 10     for (i=2; i*i<=r; ++i) {11         if (x%i == 0) {12             ret -= ret/i;13             while (x%i == 0)14                 x /= i;15         }16     }17     if (x > 1)18         ret -= ret/x;19     return ret;20 }21 22 int main() {23     int n, k;24     int i, j;25     __int64 ans, tmp;26 27     while (scanf("%d %d", &n, &k) != EOF) {28         if (n==1 || k==2)29             printf("1\n");30         else if (k==1) {31             ans = 0;32             for (i=1; i*i<=n; ++i) {33                 if (n%i == 0) {34                     j = n/i;35                     tmp = getNotDiv(i)*getNotDiv(j)%MOD;36                     if (j == i) {37                         ans += tmp;38                     } else {39                         ans += tmp<<1;40                     }41                     ans %= MOD;42                 }43             }44             printf("%I64d\n", ans%MOD);45         } else {46             printf("0\n");47         }48     }49 50     return 0;51 }

 

【HDOJ】4983 Goffi and GCD


联系
我们