http://acm./showproblem.php?pid=5514
没有想到怎么利用gcd的性质来改进指数级别的容斥，还是没有理解容斥的思想，只知道基础的。
已经知道结果就在因数之中，只要计算因数可以算几次就可以了。
代码：
#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int maxn = 10005;int yinshu[maxn];int a[maxn];int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int used[maxn],vis[maxn];int main(){int t,i,j;int n,m;scanf("%d",&t);int icase=0;while(t--){memset(used,0,sizeof(used));memset(vis,0,sizeof(vis));scanf("%d%d",&n,&m);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)a[i]=gcd(a[i],m);int cnt=0;for(i=1;i*i<=m;i++){if(m%i==0){yinshu[cnt++]=i;if(i*i!=m)yinshu[cnt++]=m/i;}}sort(yinshu,yinshu+cnt);sort(a,a+n);for(i=0;i<cnt;i++){for(j=0;j<n;j++)if(yinshu[i]%a[j]==0){vis[i]=1;break;}} ll ans=0;for(i=0;i<cnt;i++){if((vis[i]-used[i])==0)continue;ll tmp=(m-1)/yinshu[i];ans+=(tmp+1)*tmp/2*yinshu[i]*(vis[i]-used[i]);for(j=i+1;j<cnt;j++){if(yinshu[j]%yinshu[i])continue;used[j]+=vis[i]-used[i];}}printf("Case #%d: %lld\n",++icase,ans);}// cout << "Hello world!" << endl;return 0;}
