【BZOJ】【2694】Lcm

数论/莫比乌斯反演/线性筛

　　题解：http://www.cnblogs.com/zyfzyf/p/4218176.html

　　JZPTAB的加强版？感觉线性筛好像还是不怎么会啊……sad

　　题目记下来，回头再复习复习

 1 /**************************************************************
 2     Problem: 2694
 3     User: Tunix
 4     Language: C++
 5     Result: Accepted
 6     Time:1868 ms
 7     Memory:52052 kb
 8 ****************************************************************/
 9  
10 //BZOJ 2694
11 #include<vector>
12 #include<cstdio>
13 #include<cstring>
14 #include<cstdlib>
15 #include<iostream>
16 #include<algorithm>
17 #define rep(i,n) for(int i=0;i<n;++i)
18 #define F(i,j,n) for(int i=j;i<=n;++i)
19 #define D(i,j,n) for(int i=j;i>=n;--i)
20 using namespace std;
21 typedef long long LL;
22 inline int getint(){
23     int r=1,v=0; char ch=getchar();
24     for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-1;
25     for(; isdigit(ch);ch=getchar()) v=v*10-'0'+ch;
26     return r*v;
27 }
28 const int N=4e6+10;
29 /*******************template********************/
30  
31 int mu[N],prime[N],g[N],tot;
32 bool check[N];
33 void getmu(){
34     int n=N-3;
35     g[1]=1;
36     F(i,2,n){
37         if (!check[i]){
38             prime[++tot]=i;
39             g[i]=i-i*i;
40         }
41         F(j,1,tot){
42             int k=i*prime[j];
43             if (k>n) break;
44             check[k]=1;
45             if (i%prime[j]) g[k]=g[i]*g[prime[j]];
46             else{
47                 int t=i/prime[j];
48                 if (t%prime[j]==0) g[k]=0;
49                 else g[k]=-g[t]*prime[j]*prime[j]*prime[j];
50                 break;
51             }
52         }
53     }
54     F(i,0,n) g[i]+=g[i-1];
55 }
56 inline int sum(int n,int m){
57     return n*(n+1)*m*(m+1)/4;
58 }
59 int main(){
60 #ifndef ONLINE_JUDGE
61     freopen("2694.in","r",stdin);
62     freopen("2694.out","w",stdout);
63 #endif 
64     getmu();
65     int T=getint();
66     while(T--){
67         int n=getint(),m=getint(),ans=0;
68         if (n>m) swap(n,m);
69         for(int i=1,next;i<=n;i=next+1){
70             next=min(n/(n/i),m/(m/i));
71             ans+=sum(n/i,m/i)*(g[next]-g[i-1]);
72         }
73         printf("%d
",ans&1073741823);
74     }
75     return 0;
76 }

View Code

2694: Lcm

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 247 Solved: 105
[Submit][Status][Discuss]

Description

对于任意的>1的n gcd(a, b)不是n^2的倍数
也就是说gcd(a, b)没有一个因子的次数>=2

Input

一个正整数T表示数据组数

接下来T行每行两个正整数表示N、M

Output

T行每行一个整数表示第i组数据的结果

Sample Input

4
2 4
3 3
6 5
8 3

Sample Output

24
28
233
178

HINT

HINT

T <= 10000

N, M<=4000000

Source

[Submit][Status][Discuss]