Sum

    xiaoxiao2021-03-26  6

    Sum

    时间限制: 1000 ms  |  内存限制: 65535 KB 难度: 3 描述

                给你一个数N,使得在1~N之间能够找到x使得x满足gcd( x ,  N  ) >= M,

    求解gcd(x,N)的和

    输入 多组测试数据 每行输出两个数N,M(N,M不超int) 输出 输出sum 样例输入 5 3 样例输出 5

    思路:一开始想到暴力法做,超时 ,后来借鉴学长经验AC:

    大致思路: 用欧拉函数求 ,euler(n) 表示 1到n与n互质的数的个数,  如果n能够被 i 整除 ,

             则euler(n/i)等价于gcd(x,N)==i 的个数  (x是从1到n的所有数字)。

    所以,你会想到一个for循环,因为gcd(x,N)的值为1到n  枚举  gcd为M到n,再来求和? 时间复杂度也会很高,

    所以并不需要全部一一枚举 

            比如gcd(x,N)  N为  10  , 它们的gcd  只有  1,10    2,5

                                        N为15    它们的gcd  有  1,15,   3,5   

           所以它们的gcd  只需要知道1  到 根号n 而另外一个gcd   为  n/i  ;

    for(i=1;i*i<=n;i++) { if(n%i==0) { if(i>=m) sum+=i*euler(n/i); if(i*i!=n&&n/i>=m) sum+=(n/i)*euler(i); } }

    #include<stdio.h> #include<iostream> #include<string.h> using namespace std; #include<stdio.h> #include<math.h> int b[1000]; int we(int n)//求欧拉函数 { memset(b,0,sizeof(b)); long long int i,j; long long int g; g=n; int m=0; for(i=2; i*i<=n; i++) { if(n&&n%i==0) { b[m++]=i; while(n&&n%i==0) n/=i; } } if(n!=1) { b[m++]=n; } long long int sum=1,ni=1; for(long long int i=0; i<m; i++) { sum=sum*(b[i]-1); ni=ni*b[i]; } return sum*g/ni; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=-1) { long long int sum=0; for(int i=1; i*i<=n; i++) { if(n%i==0) { if(i>=m) sum+=i*we(n/i); if(i*i!=n&&n/i>=m) sum+=(n/i)*we(i); } } printf("%lld\n",sum); } }
    转载请注明原文地址: https://ju.6miu.com/read-500054.html

    最新回复(0)