HDU 5514(Frogs-与n互质的数的求和)

给一个数列ai|m(1≤m≤109),

对<m<script type="math/tex" id="MathJax-Element-5724"> ai的倍数的数,求和

先把重复的数，倍数关系的数去掉。

显然m的因子不超过200个，令D为m的因子集合

此时ai均为m的因子，

赛场上可以O(2n) 暴力

但hdu上不行

考虑O(|D|2)

我们把[0,m−1]的整数x, 按gcd(x,m)=d分类

显然每个集合中的数要么全取，要么不取

对每个d，取的代价是d*(小于m/d且与它互质的数的和)

d=d∗phi(m/d)∗m/d/2=m∗phi(m/d)/2

如何对<t<script type="math/tex" id="MathJax-Element-5738"> ai求和？

注意由于 gcd(a,b)=gcd(a−b,b) ，

答案= tϕ(t)2

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<functional>

#include<cmath>

#include<vector>

#include<map>

#include<iostream>

#include<queue>

using namespace std;

typedef long long ll;

#define For(i,n) for(int i=1;i<=n;i++)

#define Rep(i,n) for(int i=0;i<n;i++)

#define Fork(i,k,n) for(int i=k;i<=n;i++)

#define pb push_back

#define MAXN (1000000)

 

int gcd(int a,int b){if (!b) return a; else return gcd(b,a%b);}

int lcm(int a,int b){if (a==0) return b; return a/gcd(a,b)*b;}

int n,m,a[MAXN];

vector<int> v;

vector<int> v2;

bool b[MAXN];

ll ans=0;

int t2;

void dfs(int l,int x,int s) {

    if (l==t2) {

        if (x==0) return;

        ll p2=(ll)x*(1+(ll)(m-1)/x)*(ll)((m-1)/x)/2;

        if (s&1) ans+=p2; else ans-=p2;

        return;

    }

    dfs(l+1,lcm(x,v2[l]) ,s+1);

    dfs(l+1,x,s);

}

ll phi(int m){

    if (m==1) return 1;

    int ans=m;

    for(int d=2;d*d<=m;d++) {

                if (m%d==0) {

                    ans=ans*(ll)(d-1)/(ll)d;

                } 

                while (m%d==0) m/=d;

        }

    if (m>1) ans=ans*(ll)(m-1)/(ll)m;

    return ans;

}

ll sum_phi(int t)

{

}

map<int,int> h;

int main() {

    int T;cin>>T;

    For(kcase,T)

    {

        v.clear();

        v2.clear();

        ans=0;

        cin>>n>>m;

        For(i,n) scanf("%d",&a[i]),a[i]=gcd(a[i],m);

        sort(a+1,a+1+n);

        n=unique(a+1,a+1+n)-(a+1);

 

 

        if (a[1]==1) {

            printf("Case #%d: %lld\n",kcase,(ll)(m)*(ll)(m-1)/2);

            continue;

        }

 

        for(int d=1;d*d<=m;d++) {

                if (m%d==0) {

                    v.pb(d);

                    if (d*d<m) v.pb(m/d);

                } 

        }

        int t=v.size();

        Rep(j,t) b[j]=0;

 

        h.clear();

        For(i,n) {

            if (h.find(a[i])!=h.end()) continue;

            Rep(j,t) {

                if (b[j]) continue;

                if (a[i]==v[j]) {

                    v2.pb(a[i]);

                }

                if (v[j]%a[i]==0) {

                    b[j]=1;

                    h[v[j]]=1;

                }

            }

        }

 

 

        t2=v2.size();

//        Rep(i,t2) cout<<v2[i]<<' ';cout<<endl;

//        Rep(i,t) cout<<v[i]<<' ';cout<<endl;

 

        // For(i,100) cout<<phi(i)<<' ';cout<<endl;

 

        Rep(i,t) {

            Rep(j,t2) {

                if (v[i]%v2[j]==0) {

                    ll d=v[i];

                    if (m/d==1) ans+=0;

                    else ans+= (ll)(phi(m/d))*m/2;

                    //cout<<v[i]<<' '<<ans<<endl;

                    break;

                }

            }

        }    

 

 

        printf("Case #%d: %lld\n",kcase,ans);

    }

 

    return 0;

}