ACM-ICPC 2018 沈阳赛区网络预赛G-Spare Tire

 

说起来这题和这个挺像的传送门区别就是推导出来的函数不太一样，其他差不多一样

 

推导，得出通项an = n*(n+1)

对于ap+a2p+a3p+******+akp = p*(k+1)*k/2 +p*p* k*(k+1)*(2*k+1)/6

特别的：p = 1，即{an}的前n项和 = (k+1)*k/2 + k*(k+1)*(2*k+1)/6

那么将m唯一分解，用容斥原理即可，比赛的时候1&(i>>j)忘记写1&了，wa了十几发。。最后几分钟才过。。

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int vis[100000];
int prim[1300],pr_m[130],Pr_cnt;
int cnt,Pr_n = 10000;
ll n,m;
const ll mod = 1e9+7;
const ll Six = 166666668;
const ll Two = 500000004;
inline ll Mod(ll a,ll b){
    return (a%mod)*(b%mod)%mod;
}
inline ll F(ll x,ll k){
    return (Mod(x,x)*Mod(Mod(k,k+1),Mod(k+k+1,Six))%mod + Mod(Mod(1+k,k),Mod(x,Two)) )%mod;
}
void Eulerprim()
{
    for(int i=2;i<=Pr_n;i++)
    {
        if(!vis[i])
            prim[++cnt] = i;
        for(int j=1;j<=cnt&&prim[j]*i<=Pr_n;j++)
        {
            vis[prim[j]*i] = 1;
            if(i%prim[j]==0)
                break;
        }
    }
}
void sovle()
{
    ll tm = n;
    Pr_cnt = 0;
    for(int i=1;i<cnt;i++)
    {
        if(prim[i]>m)
            break;
        if(m%prim[i]==0)
        {
            pr_m[Pr_cnt++] = prim[i];
            while(m%prim[i]==0)
                m/=prim[i];
        }
    }
    if(m>1)
        pr_m[Pr_cnt++] = m;

    ll ans = F(1LL,n),sum = 0;

    int tx = 1<<Pr_cnt;

    for(int i=1;i<tx;i++)
    {
        int cc = 0;
        ll x = 1;
        for(int j=0;j<Pr_cnt;j++)
            if(1&(i>>j))cc++,x*=pr_m[j];
        if(cc&1)
            sum = (sum + F(x,tm/x) )%mod;
        else
            sum = ((sum - F(x,tm/x))%mod + mod )%mod;
    }
    printf("%lld\n",((ans - sum)%mod + mod )%mod);
}
int main()
{
    Eulerprim();
    while(~scanf("%lld%lld",&n,&m))
        sovle();
    return 0;
}