BZOJ 2154(모비우스 역극)
1351 단어 조합 수학
OIer 문제는 재미없는데, 이 녀석들에게 정말 탄복한다.
init를 초기화할 때 for는 maxn까지 바로 열 수 없습니다. 이치대로라면 그럴 수 없지만, 확실히 T입니다.
#include
using namespace std;
typedef long long ll;
const ll mod=20101009;
const int maxn=1e7+10;
bool vis[maxn];
int prime[maxn];
ll pre[maxn],g[maxn],inv[5];
int n,m;
void init(){
inv[1]=1,g[1]=1,pre[1]=1;
int tot=0;
for(int i=2;i<=n;i++){
if(!vis[i]){
prime[tot++]=i;
g[i]=1-i;
}
for(int j=0;jn){
break;
}
vis[i*prime[j]]=1;
if(i%prime[j]==0){
g[i*prime[j]]=g[i];
break;
}else{
g[i*prime[j]]=g[i]*(1-prime[j]);
}
}
pre[i]=(pre[i-1]+1ll*g[i]*i%mod+mod)%mod;
}
for(int i=2;i<=4;i++){
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
}
int main(){
scanf("%d%d",&n,&m);
ll ans=0;
if(n>m) swap(n,m);
init();
for(int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
if(r>n) r=n;
ans+=(pre[r]-pre[l-1]+mod)%mod*inv[4]%mod*(n/l)%mod*(m/l)%mod*(n/l+1)%mod*(m/l+1)%mod;
ans%=mod;
}
printf("%lld
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ4665: 작은 w의 결혼 사탕[dp, 용기...QwQ가 만든 첫 번째 이런 문제 f[i][j]는 전 i종을 분배한 것을 나타낸다. 적어도 j 개인이 합법적이지 않다는 것을 의미한다. 그리고 한 번 질책하면 된다. 마지막으로 통계를 낼 때 남은 n-j 개인의...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.