首页 > 代码库 > 【HDOJ】4983 Goffi and GCD
【HDOJ】4983 Goffi and GCD
题意说的非常清楚,即求满足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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。