題目大意：對于任意的>1的n gcd(a, b)不是n^2的倍數(shù)，的1到a和1到b的lcm(a,b)之和。 題解：又是一道變態(tài)題。。。。。。。。。。 可以參考同系列的上一篇文章，這題主要的特殊處在于不能出現(xiàn)gcd(a,b)為n^2倍數(shù)的lcm(a,b)，通過一頓瞎搞我們發(fā)現(xiàn)最后要求的前綴和中多出了一個abs（u（D/i）），這還是一個積性函數(shù)，唯一不同的是i中包含PRime[j]的情況，這個我們就找規(guī)律，如果一個數(shù)中包含三個一樣的因子的話無論如何兩個u中一定有一個包含兩個一樣的因子，那么表達式為0，所以出現(xiàn)這種情況的話最后一定為0。如果只有兩個一樣的因子的時候我們可以看出只有當兩個u中各包含一個該因子的時候表達式才有值，再通過這個瞎推一下就行了。
#include<cstdio>#include<cstdlib>#include<iostream>#include<iomanip>#include<ctime>#include<cmath>#include<cstring>#include<string>#include<algorithm>using namespace std;int sum[4001000];int prime[400100];bool pd[4001000];int top=0;void shai(){ sum[1]=1; for(int i=2;i<=4000000;i++) { if(!pd[i]) { prime[++top]=i; sum[i]=i-i*i; } for(int j=1;i*prime[j]<=4000000;j++) { pd[i*prime[j]]=true; if(i%prime[j]==0) { int x=i/prime[j]; if(x%prime[j]==0) sum[i*prime[j]]=0; else sum[i*prime[j]]=-prime[j]*prime[j]*prime[j]*sum[x]; break; } sum[i*prime[j]]=sum[i]*sum[prime[j]]; } } for(int i=1;i<=4000000;i++) { sum[i]=sum[i]+sum[i-1]; }}inline int Sum(int x,int y){ int mid1=x*(x+1)/2; int mid2=y*(y+1)/2; return mid1*mid2;}int solve(int n,int m){ int last; int limit=min(n,m); long long re=0; for(int i=1;i<=limit;i=last+1) { last=min(n/(n/i),m/(m/i)); re=re+(sum[last]-sum[i-1])*Sum(n/i,m/i); } return re;}int main(){ //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); shai(); int T; scanf("%d",&T); int n,m; while(T--) { scanf("%d%d",&n,&m); long long ans=solve(n,m); printf("%d/n",ans&((1<<30)-1)); } return 0;}新聞熱點
疑難解答
