题意：给出n和m，代表有n只青蛙和m颗标号为0~m-1的石子，m颗石子围成一个圈，给出n个数据a_i表示一只青蛙一次能跳多少步，求最终所有被青蛙踩过的石子的标号和。

1<=N<=10000，1<=m<=1e9,1<=a_i<=1e9;共1~20组数据，1000MS

算法/思路：容斥原理：首先为了方便处理，将a_i变为gcd(a_i,m)（用数论知识可以证明结果不变），然后使用容斥原理，当然不能用2ⁿ那么多次操作的方法，于是有一个较为巧妙的方法，求出m的所有因子(约为log₂m个)，并从小到大排序，然后对第i个因子，依次判断每个a_i是否有经过它，有则将vis[i]记为1，否则为0，并将所有num[i]初始化为0(num数组用于表示某数用过多少次)，最后从小到大扫描每个因子A_i，令ans+=(vis[i]-num[i])*(A_i*(m/A_i-1)/2)，并扫描所有比A_i大的因子A_k，若A_k是A_i的倍数，则num[k]+=(vis[i]-num[i])，这样显然每个数最终只使用一次(相当于容斥时直接判断数被重复利用了几次)。算法复杂度O(log₂m(n+log₂m))

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std; const int maxn=10005; int t,n,m,sq,tot;int a[maxn+5];vector
           
             vis,num;vector
            
              x;long long ans; int gcd(int x,int y){ if (y==0) return x;else return gcd(y,x%y);} void init(){ x.clear();tot=1;ans=0; vis.clear();num.clear(); scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%d",&a[i]);} int main(){ scanf("%d",&t); for (int q=1;q<=t;++q){ init(); sq=floor(sqrt(m)+0.5); x.push_back(1);//故初始化tot=1; for (int i=2;i<=sq;++i) if (m%i==0){ x.push_back(i);++tot; if (m/i==i) continue; x.push_back(m/i);++tot; } vis.resize(tot,0);num.resize(tot,0); //for (int i=0;i