BZOJ 3309 DZY Loves Math

题面：

3309: DZY Loves Math

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 1086 Solved: 651
[Submit][Status][Discuss]

Description

对于正整数n，定义f(n)为n所含质因子的最大幂指数。例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0。
给定正整数a,b，求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b)。

Input

第一行一个数T，表示询问数。
接下来T行，每行两个数a,b，表示一个询问。

Output

对于每一个询问，输出一行一个非负整数作为回答。

Sample Input

4
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957

Sample Output

35793453939901
14225956593420
4332838845846
15400094813

HINT

【数据规模】
T<=10000
1<=a,b<=10^7

题意是求

$sum_{i=1}^{n}sum_{j=1}^{m}f(gcd(i,j))$

$=sum_{d=1}^{min(n,m)}f(d)sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=d]$

$=sum_{d=1}^{min(n,m)}f(d)sum_{i=1}^{lfloorfrac{n}{d} floor}sum_{j=1}^{lfloorfrac{m}{d} floor}[gcd(i,j)=1]$

$=sum_{d=1}^{min(n,m)}f(d)sum_{i=1}^{lfloorfrac{n}{d} floor}sum_{j=1}^{lfloorfrac{m}{d} floor}sum_{p|gcd(i,j)}mu(p)$

$=sum_{d=1}^{min(n,m)}f(d)sum_{i=1}^{lfloorfrac{n}{d} floor}sum_{j=1}^{lfloorfrac{m}{d} floor}sum_{p|i,p|j}mu(p)$

$=sum_{d=1}^{min(n,m)}f(d)sum_{i=1}^{lfloorfrac{n}{pd} floor}sum_{j=1}^{lfloorfrac{m}{pd} floor}mu(p)$

$=sum_{T=1}^{min(n,m)}lfloorfrac{n}{T} floorlfloorfrac{m}{T} floorsum_{d|T}f(d)mu(frac{T}{d})$

令$g(T)=sum_{d|T}f(d)mu(frac{T}{d})$,$T=p_{1}^{k_{1}}*p_{2}^{k_{2}}cdots p_{n}^{k_{n}}$

当存在$k_{i} eq k_{j}$时,我们将$p_{i}$按$k_{i}$最大和非最大分为$A$和$B$两个集合。

则对于$A$中每个选取方案,$B$中$mu$值和为$0$,即存在$k_{i} eq k_{j}$时,$g(T)=0$

当$k_{1}=k_{2}= cdots =k_{n}=k$时,只有每个质因子都选择$k-1$个时才会对答案造成贡献,此时$g(T)=(k-1)*(-1)^(n+1)$,

之后线筛+分块搞就好了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #define maxn 10000000
 4 #define LL long long
 5 using namespace std;
 6 int prime[670000],last[maxn+10],t[maxn+10];
 7 bool book[maxn+10];
 8 LL g[maxn+10],cnt;
 9 void init()
10 {
11     for(int i=2;i<=maxn;i++)
12     {
13         if(!book[i])
14         {
15             prime[++cnt]=i;
16             last[i]=t[i]=g[i]=1;
17         }
18         for(int j=1;j<=cnt&&1LL*prime[j]*i<=maxn;j++)
19         {
20             book[prime[j]*i]=true;
21             if(i%prime[j]==0)
22             {
23                 last[i*prime[j]]=last[i];
24                 t[i*prime[j]]=t[i]+1;
25                 if(last[i]==1)
26                     g[i*prime[j]]=1;
27                 else
28                     g[i*prime[j]]=(t[last[i]]==t[i*prime[j]]?-g[last[i]]:0);
29                 break;
30             }
31             last[i*prime[j]]=i;
32             t[i*prime[j]]=1;
33             g[i*prime[j]]=(t[i]==1?-g[i]:0);
34         }
35     }
36     for(int i=2;i<=maxn;i++)
37             g[i]+=g[i-1];
38 }
39 int T;
40 int n,m;
41 LL query(int n,int m)
42 {
43     LL ans=0;
44     if(n>m)
45         swap(n,m);
46     int j;
47     for(int i=1;i<=n;i=j+1)
48     {
49         j=min(n/(n/i),m/(m/i));
50         ans+=(g[j]-g[i-1])*(n/j)*(m/j);
51     }
52     return ans;
53 }
54 int main()
55 {
56     init();
57     scanf("%d",&T);
58     while(T--)
59     {
60         scanf("%d%d",&n,&m);
61         printf("%lld
",query(n,m));
62     }   
63 }

BZOJ 3309