ACM-ICPC 2018 沈阳赛区网络预赛 G
程序员文章站
2022-03-13 15:46:12
...
打表可以发现an是n*(n+1)
进而推出求和公式
容斥一下,代码如下
#include<cstdio>
#include<cstring>
using namespace std;
const long long mod=1e9+7;
int prime[33],pn;
long long n,m;
long long q_pow(long long a,long long b)
{
long long ans=1;
while(b){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
long long sum(long long s,long long n)
{
long long temp1=(s*s)%mod,temp2=s;
temp1=(temp1*n)%mod;
temp1=(temp1*(n+1))%mod;
temp1=(temp1*(2*n+1))%mod;
temp1=(temp1*q_pow(6,mod-2))%mod;
temp2=(temp2*n)%mod;
temp2=(temp2*(1+n))%mod;
temp2=(temp2*q_pow(2,mod-2))%mod;
long long ans=(temp1+temp2)%mod;
return ans;
}
long long calc(long long n){
long long res=0;
for(int i=1; i<(1<<pn); ++i){
long long tmp=1,cnt=0;
for(int j=0; j<pn; ++j){
if(((i>>j)&1)==0) continue;
++cnt;
tmp*=prime[j];
}
long long ans=sum(tmp,n/tmp);
if(cnt&1) res=(res+ans)%mod;
else res=(res-ans+mod)%mod;
}
return res;
}
int main(){
while(~scanf("%lld%lld",&n,&m)) {
pn=0;
for(int i=2; i*i<=m; ++i){
if(m%i) continue;
while(m%i==0) m/=i;
prime[pn++]=i;
}
if(m!=1) prime[pn++]=m;
long long ans=sum(1,n);
// printf("%lld\n",ans);
ans=(ans-calc(n)+mod)%mod;
printf("%lld\n",ans);
}
}
推荐阅读
-
ACM-ICPC 2018 徐州赛区网络预赛 H - Ryuji doesn't want to study
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study(线段树区间求和)
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study—— 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 H Ryuji doesn't want to study(线段树 两种做法)
-
【ACM-ICPC 2018 徐州赛区网络预赛】H题 Features Track ---- 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (线段树维护)
-
2018 沈阳赛区网络预赛 F. Fantastic Graph 有上下界可行流
-
ACM-ICPC 2018 徐州赛区网络预赛 Trace
-
Trace-----ACM-ICPC 2018 徐州赛区网络预赛
-
ACM-ICPC 2018 沈阳赛区网络预赛 F题 Fantastic Graph