【2015沈阳区域赛】Frogs

大意：

$有m个石头，标号从0\sim m-1，有n只青蛙，所有青蛙一开始都在编号为0的石头上$
$每只青蛙每次可以跳的距离为a[i]，求所有青蛙能够占领的石头的编号之和$

$思路：$
$每个青蛙可以跳的位置应该是gcd(a[i]，m)的倍数$
$如果gcd(a[i],m)|x,石子x会被第i个青蛙踩到$
$gcd(a[i],m)|x表示后者是前者的倍数$
$sum(q)=\frac{\phi (q)*q}{2}$
$sim(q)是1\sim q-1与q互质的数的和，\phi (q)是1\sim q-1与q互质的数的个数$
$可以特判gcd(a[i],m)==1，这时答案就是\frac{m*(m-1)}{2}$

欧拉函数求和+思维

$当m=20，a[]=2,5$
$如果枚举a[i]的贡献求和，会出现重复计算$
$可以考虑枚举m的每个因子的贡献（这个原理我没搞清楚，网上也没看到有人解释）$
$m的因子有2、4、5、10$
$石子x=2青蛙可以踩到，贡献是2*(1+3+7+9)$
$即2*\frac{\phi (\frac{20}{2})*\frac{20}{2}}{2}$
$1\sim 9与10互质的数是1、3、7、9，这样得到的数与2的乘积不会大于等于m，同时也不会和其它因子得到的值重复$
$石子x=4青蛙可以踩到，贡献是4*(1+2+3+4)$
$即4*\frac{\phi (\frac{20}{4})*\frac{20}{4}}{2}$
$x=5、10同上$
$即，如果x能被踩到，贡献就是\frac{\phi (\frac{m}{x})*m}{2}$
$可以发现这样统计很巧妙，不会有重$
$复杂度O(\sqrt{m}*\sqrt[4]{m})$
$My Code:$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;
ll com[maxn];
ll t,n,m,ans;
ll euler(ll x) {
    ll ans = x;
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            ans = ans / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x != 1) ans = ans / x * (x - 1);
    return ans;
}
bool check(ll x) {
    for(int i = 0; i < n; i++)
        if(x%com[i] == 0)
            return true;
    return false;
}
int main() {
    cin>>t;
    for(ll cas=1;cas<=t;++cas,ans=0) {
        bool Prime = false;
        cin>>n>>m;
        for(ll i=0,x,g;i<n;++i) {
            cin>>x;
            com[i]=__gcd(x,m);
            if(com[i] == 1) Prime = true;
        }
        if(Prime) ans = m*(m-1)/2;
        else {
            for(int i = 2; i*i <= m; i++) if(m%i == 0){
                if(check(i)) ans += euler(m/i)*m/2;
                if(i*i!=m && check(m/i)) ans+= euler(i)*m/2;
            }
        }
        printf("Case #%lld: %lld\n",cas,ans);
    }
}

容斥原理

$如果不考虑重复计算，步长step的贡献为m*\frac{\frac{m}{step}-1}{2}$
$考虑到会重复计算，如果m的因子x青蛙能踩到，在计算前用cnt[x]=1标记x应该被算一次$
$计算时从小到大遍历m的因子，tmp=cnt[i]-sum[i]表示i及i的倍数对答案的贡献情况$
$如果tmp<0表示i及i的倍数被多加了tmp次，tmp=1表示i及i的倍数还没被计算,tmp=0表示i及i的倍数已经计算或者没有贡献$
$1故m的因子i的贡献为m*\frac{\frac{m}{step}-1}{2}*(cnt[i]-sum[i])$
$加一次x，sum[k]就加一次，减一次x，sum[k]就减一次，表示x实际被加了几次，k为x的倍数$
$计算完一个因子i后维护i的倍数的sum[]数组，sum[k]+=cnt[i]-sum[i]$
$不考虑输入，复杂度O((log _{2}m)^{2})$
$My Code:$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>v;
const int maxn=1e5+5;
ll cnt[maxn],sum[maxn];
int main(void) {
    ll t,n,m;
    cin>>t;
    for(int cas=1;cas<=t;++cas) {
        cin>>n>>m;
        memset(cnt,0,sizeof cnt);
        memset(sum,0,sizeof sum);
        v.clear();
        for(int i=2;i*i<m;++i) if(m%i==0) {
            v.push_back(i);
            v.push_back(m/i);
        }
        v.push_back(1);
        sort(v.begin(),v.end());
        for(ll i=1,x,g;i<=n;++i) {
            cin>>x;
            g=__gcd(x,m);
            for(int j=0;j<v.size();++j) if(v[j]%g==0)
                cnt[j]=1;
        }
        ll res=0;
        for(int i=0;i<v.size();++i) {
            res+=m*(m/v[i]-1)/2*(cnt[i]-sum[i]);
            for(int j=i+1;j<v.size();++j) {
                if(v[j]%v[i]==0) sum[j]+=cnt[i]-sum[i];
            }
        }
        printf("Case #%lld: %lld\n",cas,res);
    }
}