370

题目在http://acm.sgu.ru/problem.php?contest=0&problem=370
首先特判掉n=1或m=1或n、m都等于1的情况。。
然后答案就是p<=n&&p<=m&&(p,q)=1的数对的个数。。
很明显可以用容斥原理做。。
就OK了。。

#include<iostream>#include<vector>#include<algorithm>#include<cstring>using namespace std;const int maxn=1000000+1;int n,m,pnt,*P;long long ans=0;int S[maxn][10],D[maxn]={};void dfs(int p,int ch,int now){ if(now>n)return; if(p==pnt) { if(ch&1)ans-=n/now; else ans+=n/now; return; } dfs(p+1,ch,now); dfs(p+1,ch+1,now*P[p]);}int main(){ //freopen("in","r",stdin); cin>>n>>m;n–;m–; if(m>n)swap(n,m); if(!n){cout<<0<<endl;return 0;} if(!m){cout<<1<<endl;return 0;} for(int i=1;i<=m;i++) { if(i==1){ans+=n;continue;} int t=i,a;P=S[i]; for(a=2;a*a<=t;a++) if(t%a==0) { while(t%a==0){t/=a;} break; } if(t==i)P[D[i]++]=t; else { D[i]=D[t]+1; memcpy(P,S[t],sizeof(S[t])); P[D[i]-1]=a; } pnt=D[i]; dfs(0,0,1); } cout<<ans+2<<endl;}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>