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;
}