jzptab

Source and Judge

bzoj2693

Record

2h

Analysis

请先思考后再展开

建议先做yy的gcd数表

感觉这道题是po姐ppt里面最综合的一道题
考虑枚举公约数tt,反演其乘积
$a=\lfloor \frac{n}{d} \rfloor,b=\lfloor \frac{m}{d} \rfloor$
$F(d)=a(1+a)b(b+1)/4 \cdot d^2$
然后把gcd放缩,但因为这次求乘积,要还原
$ans=\sum_{tt} tt ( \sum_d \mu(d) \cdot F(d) )$ (F中n=n/tt)
套路的换元应对多组数据
$T=tt \cdot d$
$$
ans=\sum_T
\lfloor \frac{n}{T} \rfloor (\lfloor \frac{n}{T} \rfloor+1)/2
\lfloor \frac{m}{T} \rfloor (\lfloor \frac{m}{T} \rfloor+1)/2
\times
( \sum_{d|T} \mu(d) T \cdot d )
$$
然后后面那个是积性函数,随便记录一个质数幂,就可以筛了
时间复杂度为 $O(n+T \sqrt n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MOD=1e8+9;//not prime!
ll add(ll a,ll b)
{
a%=MOD;b%=MOD;
a+=b;a%=MOD;
if(a<0) a+=MOD;
if(a>=MOD) a-=MOD;
return a;
}
const int MAX_NUM=1e7+1;
bool no[MAX_NUM];
int pr=0,prime[MAX_NUM/10];
ll sum[MAX_NUM];
int gg[MAX_NUM];//任意一个p^k
void pre()
{
sum[1]=1;gg[1]=1;
for(int i=2;i<MAX_NUM;i++)
{
if(no[i]==0) prime[++pr]=i,sum[i]=add(i,-(ll)i*i),gg[i]=i;
for(int j=1;j<=pr and (ll)i*prime[j]<MAX_NUM;j++)
{
int to=i*prime[j];
no[to]=1;
if(i%prime[j]==0)
{
if(gg[i]%prime[j]==0) gg[to]=gg[i]*prime[j];
else gg[to]=gg[i];
if(gg[to]==to) sum[to]=add(to,-(ll)to*prime[j]);
else sum[to]=sum[gg[to]]*sum[to/gg[to]]%MOD;
break;
}
gg[to]=gg[i];
sum[to]=sum[i]*sum[prime[j]]%MOD;
}
}
for(int i=1;i<MAX_NUM;i++) sum[i]=add(sum[i-1],sum[i]);
}
void main()
{
pre();
int T;scanf("%d",&T);
while(T--)
{
int n,m;scanf("%d%d",&n,&m);
ll ans=0;
for(int t=1;t<=n and t<=m;)
{
ll a=n/t,b=m/t;
int lst=min(n/a,m/b);
ans=add(ans,(a*(a+1)/2%MOD)*(b*(b+1)/2%MOD)%MOD*add(sum[lst],-sum[t-1])%MOD );
t=lst+1;
}
printf("%lld\n",ans);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6322.html
转载请注明出处,谢谢!