一道洛谷比赛题,当时还没学太多知识,当时利用了下人类智慧,水了80分。
emm...比出题人意料的80分做法天差地别,好像还挺简单的....
题意很明确,反演后直接杜教筛即可。
出题人:zhoutb2333

题目背景

ZRQ 是一名伟大的科学家,他此行的目的是寻找一些矿石回去研究。

现在他来到了一座矿洞前。

题目来源:zhoutb2333

题目描述

ZRQ 发现矿洞是一个 大小的点阵, 每个点形如 (x,y),1x,yN(x,y),1 \le x,y \le N

为了进行有价值的研究,ZRQ 要把矿洞分析得十分透彻,他要分析整个矿洞的总体价值,以确定这个矿洞有没有价值去探索。

每个点 (x,y)(x,y) 有一个价值 Vx,yV_{x,y} ,山洞的价值定义为 x=1Ny=1Nφ(Vx,y)\sum^{N}_{x=1} \sum^{N}_{y=1} \varphi(V_{x,y}) ,其中 φ(n)\varphi (n) 表示小于等于 nn 并与 nn 互质的数的个数, φ(1)=1\varphi(1)=1

ZRQ 现在站在 (0,0)(0,0) 位置,他会把所有能看到的点都标记一遍。能看到点 (x,y)(x,y) 定义为 (0,0)(0,0)(x,y)(x,y) 的连线上不存在其他整点。

ZRQ 向每个被标记过的点发射一束激光,激光会穿过点并无限延伸。显然每个点只会被一条激光穿过,无论是否被标记。

一个点 (x,y)(x,y) 的价值 Vx,yV_{x,y} 被他定义为 (x+yx0+y0)2(\frac{x+y}{x_0+y_0})^2 。其中 (x0,y0)(x_0,y_0) 表示所有穿过这个点的激光所穿过的第一个点的坐标。

比如说点 (3,6)(3,6) ,被 y=2xy=2x 穿过,穿过的第一个点为 (1,2)(1,2) 。所以它的价值是 (3+61+2)2=9(\frac{3+6}{1+2})^2=9

ZRQ 现在问你,这个山洞的价值是多少。当然,因为结果可能很大,所以模 10000000071000000007 输出即可

输入输出格式

输入格式:

一行一个整数 NN

输出格式:

一行一个整数,表示答案

输入样例#1:

3

输出样例#1:

15

输入样例#2:

100

输出样例#2:

358131

说明

一共有 1010 个测试点,每个点 1010 分,计 100100 分。

对于测试点 11 ~ 33 ,有 1N1001 \le N \le 100 对于测试点 44 ~ 88 ,有 1N1000001 \le N \le 100000 对于测试点 99 ~ 1010 ,有 1N10101 \le N \le 10^{10} 对于测试点 11 ~ 88 ,时间限制为 1s1s 对于测试点 99 ~ 1010 ,时间限制为 3s3s

样例#1解释:

穿过点 (2,2)(2,2) 的激光为 y=xy=x ,穿过的第一个整点为 (1,1)(1,1) ,所以价值为 (2+21+1)2=4(\frac{2+2}{1+1})^2=4 ,同样点 (3,3)(3,3) 的价值为 (3+31+1)2=9(\frac{3+3}{1+1})^2=9 其他 77 个点的价值都是 11 ,故总价值为

其中 φ\varphi 的求法:

约定 φ(1)=1\varphi(1)=11,31,344 互质,故 φ(4)=2\varphi(4)=21,2,4,5,7,81,2,4,5,7,899 互质,故 φ(9)=6\varphi(9)=6

Solution

反演一下:

对于 ,我们考虑怎么筛:

首先有

dnnφ(d)=n\sum_{d|n}^{n}\varphi(d)=n

我们构造 i=1ni2\sum_{i=1}^{n}i^{2}

则 undefined$

杜教筛即可。

Code

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
#include <iostream>
#include <map>
#include <cmath>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
const int p=1e9+7, N=4700000, inv2=500000004, inv6=166666668;
typedef long long ll;
map<ll, ll> mp, mp2;
int cnt=0, pri[333333], phi[N+2], vis[N+2], sphi[N+2];
long long s[N+2];

inline void init(const int M) {
phi[1] = 1;
int t;
rep(i,2,M) {
if(!vis[i]) pri[++cnt]=i,phi[i]=i-1;
for(re j=1;j<=cnt&&(t=i*pri[j])<=M;++j) {
vis[t] = 1;
if(i%pri[j]==0) { phi[t]=phi[i]*pri[j];break;}
else phi[t]=phi[i]*(pri[j]-1);
}
}
rep(i,1,M) sphi[i]=(sphi[i-1]+phi[i])%p, s[i]=(s[i-1]+1ll*i*phi[i])%p;
}

inline ll Sum(ll a, ll b) { return (a+b)%p*(b-a+1)%p*inv2%p;}
inline ll calc(ll x) { x%=p; return x*(x+1)%p*(2*x+1)%p*inv6%p;}
inline ll calc2(ll x) { x%=p; return x*(x+1)/2%p;}

ll sol(ll x) {
if(x<=N) return s[x];
if(mp[x]) return mp[x];
ll res=calc(x); ll l=2, r;
for(;l<=x;l=r+1) {
r = x/(x/l);
(res-=Sum(l,r)*sol(x/l)%p)%=p;
}
return mp[x]=(res+p)%p;
}
ll Sphi(ll x) {
if(x<=N) return sphi[x];
if(mp2[x]) return mp2[x];
ll res=calc2(x); ll l=2, r;
for(;l<=x;l=r+1) {
r = x/(x/l);
(res-=1ll*(r-l+1)%p*Sphi(x/l)%p)%=p;
}
return mp2[x]=(res+p)%p;
}

long long n;

int main() {
cin >> n;
init(N);
ll l=1, r; long long ans=0;
for(;l<=n;l=r+1) {
r = n/(n/l);
(ans+=(sol(r)-sol(l-1))*(2*Sphi(n/l)-1))%=p;
}
cout << (ans+p)%p << endl;
}