题目链接： http://acm.nyist.net/JudgeOnline/problem.php?pid=471
还是直接上代码。。
#include<bits/stdc++.h>using namespace std;typedef long long LL;;];vector<]; //a[i]中存储i的所有质因数 void init(){ ;i<=N;i++) if(!vis[i]) //i->prime { a[i].push_back(i); for(int j=i+i;j<=N;j+=i) { a[j].push_back(i); vis[j]=; } }}]; //b[]中临时存储a[x]中2^a[x].size()个组合中各个数的乘积LL cal(int x,int n){ LL ret=n,g=; b[++g]=; ;i<a[x].size();i++) { int t=g; ;j<=g;j++) b[++t]=-b[j]*a[x][i],ret+=n/b[t]; g=t; } return ret;}int main(){ init(); int t;cin>>t; while(t--) { int n,m;cin>>n>>m; if(n<m) swap(n,m); LL ans=n; ;i<=m;i++) ans+=cal(i,n); cout<<ans<<endl; }}
