rt,HDU5514

题意简述：

有$n$只青蛙在$m$个编号为$0,1,..,m-1$石头上,每个青蛙每次的跳跃距离为$a_i$,问所有青蛙能到达的石头的编号和。

思路是容斥,但TLE了。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N=1e4+4;
int n,m,a[N],c;
signed main(){
	int T;cin>>T;
	while(T--){
        cin>>n>>m;
		for(int i=1;i<=n;++i)cin>>a[i],a[i]=__gcd(a[i],m);
        sort(a+1,a+1+n);
		int tot=unique(a+1,a+1+n)-a-1ll,ans=0;
//		for(int i=1;i<=tot;i++)cout<<a[i]<<" ";
//		cout<<"\n";
		for(int i=1;i<(1ll<<tot);++i){
			int num=1,cnt=0;
			for(int j=1;j<=tot;++j){
				if(i&(1ll<<j-1)){
					cnt++;
					num=num*a[j]/__gcd(a[j],num);
				}
			}
			int tmp=num;
			num=m/num;
			if(cnt%2)ans+=num*(num-1)/2*tmp;
			else ans-=num*(num-1)/2*tmp;
		}
		printf("Case #%lld: %lld\n",++c,ans);
	}
}