GCD - Extreme (II)(欧拉函数)-白红宇

GCD - Extreme (II)(欧拉函数)

阅读量：4701 次

发布时间：2019-06-09

本文共 1010 字，大约阅读时间需要 3 分钟。

b[n]表示1到n-1与n的gcd的和，所以dp[n]=dp[n-1]+dp[n];

a[i]表示与gcd(n, x)= i的x的个数；

所以b[n]=sum(a[i]*i) , 所以我们只需求a[i]即可；

根据gcd(n, x)=i --->gcd(n/i, x/i) = 1,

因此仅仅要求出欧拉函数phi(n / i)，就能够得到与n / i互质的个数；

从而求出gcd(x , n) = i的个数，这样总体就能够求解了；

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #define inf 0x3f3f3f3f#define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define sd(x) scanf("%d",&(x))#define sl(x) scanf("%lld",&(x))#define slf(x) scanf("%lf",&(x))#define scs(s) scanf("%s",s)#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)#define lowbit(x) x&(-x)#define ls now<<1#define rs now<<1|1#define lson l,mid,ls#define rson mid+1,r,rs#define int long longusing namespace std;const int maxn=5e6+10;const int N=4000001;int a[maxn],b[maxn],dp[maxn];void oula(){ //a[1]=1; for(int i=2;i