当前位置:网站首页>hdu 4983(欧拉函数)

hdu 4983(欧拉函数)

2021-07-23 14:50:13 wx60f7c9afba268

Goffi and GCD

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 992    Accepted Submission(s): 336


Problem Description
Goffi is doing his math homework and he finds an equality on his text book: gcd(na,n)×gcd(nb,n)=nk.

Goffi wants to know the number of (a,b) satisfy the equality, if n and k are given and 1a,bn.

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 (1n,k109).
 

 

Output
For each test case, output a single integer indicating the number of ( a,b) modulo 109+7.
 

 

Sample Input
2 1 3 2
 

 

Sample Output
2 1
Hint
For the first case, (2, 1) and (1, 2) satisfy the equality.
 

 

Source
 
题意:求使得成立的(a,b)的个数.
首先,我们可以知道 gcd(n,a)<=n,所以当 k>2 的时候没有这样的(a,b)
然后当 k==2 的时候我们只有一个这样的组合 (a,b) = (n,n)
接下来考虑 k=1的情况:当 k = 1时 ,gcd(n-a,n) = gcd(a,n) (这里源自gcd的变换公式) 整个式子就转换成了 gcd(a,n)*gcd(b,n)=n
设 gcd(a,n) 为 x,那么 gcd(a/x,n/x)=1,a/x 与 n/x 互质,利用欧拉函数 phi(x) 可以得到 a的个数,同理可以得到b的个数.并且x也是 n 的因子,所以在求解n的因子的同时就可以将(a,b)求出来了。
这里总结一个公式: 如果d是n的一个约数,那么1<=i<=n中 gcd(i,n) = d的个数是phi(n/d),即n/d的欧拉函数
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
typedef long long LL;
const LL mod = 1000000007;
LL phi(LL x)
{
    LL ans=x;
    for(LL i=2; i*i<=x; i++)
        if(x%i==0)
        {
            ans=ans/i*(i-1);
            while(x%i==0) x/=i;
        }
    if(x>1)
        ans=ans/x*(x-1);
    return ans;
}
LL n,k;
int main()
{
    while(scanf("%lld%lld",&n,&k)!=EOF)
    {
        if(n==1) {
            printf("1\n");
            continue;
        }
        if(k>1)
        {
            if(k==2)
                printf("1\n");
            else printf("0\n");
            continue;
        }
        LL sum = 0;
        for(LL i=1; i*i<=n; i++)
        {
            if(n%i==0)
            {
                if(i*i==n) sum = (sum+phi(i)*phi(i))%mod;
                else {
                    sum = (sum+2*phi(i)*phi(n/i))%mod;
                }
            }
        }
        printf("%lld\n",sum);
    }
    return 0;
}

 

版权声明
本文为[wx60f7c9afba268]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15309663/3154537