题意

• m块石头，n只青蛙，第i青蛙步长
• 求解所有被踩过的石头的编号(0-base)和

思路

• 观察发现，对于一只青蛙，他能踩到的石头是
• 暴力会炸
• 考虑从m入手， 的结果一定是m的因子
  • 枚举m的因子，标记是gcd倍数的因子，这些因子会产生贡献
  • 用一个cnt记录每个因子还需要计算贡献的次数
  • 从小到大计算每一个cnt不为0的因子
  • 计算完一个因子的贡献后，改因子所有的倍数因子也被计算了，所以要减去次数
  • 对于计算贡献，每个因子的贡献是 （等差数列求和，由于0-base开始，共有m/v[i]-1项，首项v[i]，公差v[i]，通项公式），再乘上自己的cnt，正值代表还没算，负值代表算多了（eg:因子有4,12,36,36就被多算了一次）

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll=long long;
//题干有问题，应该是至少被占领了一次
vector<int>V;
vector<int>a;
int cnt[201010];
signed main() {
    int n,m;
    cin >> n >> m ;
    a.resize(n+10);
    for(int i=1;i*i<=m;i++){
        if(m%i==0){
            V.push_back(i);
            V.push_back(m/i);
        }
    }
    sort(V.begin(),V.end());
    for(int i=0;i<n;i++){
        cin >> a[i];
        int g=__gcd(a[i],m);
        for(int j=0;j<V.size();j++){
            if(V[j]%g==0)cnt[j]=1;
        }
    }
    ll ans=0;
    for(int i=0;i<V.size();i++){
        if(cnt[i]!=0){
            ans+=m*(m/V[i]-1)/2*cnt[i];
            for(int j=i+1;j<V.size();j++){
                if(V[j]%V[i]==0){
                    cnt[j]-=cnt[i];
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}