题面
Sol
第一问puts("1")
第二问，\(\varphi(i^2)=i\varphi(i)\)
设\(\phi(n)=\sum_{i=1}^{n}i\varphi(i)\)根据杜教筛推的式子
\[g(1)\phi(n)=\sum_{i=1}^{n}\sum_{d|i}g(d)(\frac{i}{d})\varphi(\frac{i}{d})-\sum_{i=2}^{n}g(d)\phi(\lfloor\frac{n}{d}\rfloor)
\]
\]
设\(g(i)=i\)减号前面原式\(=\sum_{i=1}^{n}i\sum_{d|i}\varphi(\frac{i}{d})\)
\(\sum_{i|n}\varphi(i)=n\)所以就是\(\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}\)
跑杜教筛即可
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(1e6 + 1), Zsy(1e9 + 7), yyb(166666668);
IL ll Read(){
RG ll x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int prime[_], num;
ll phi[_];
map <int, int> Phi;
bool isprime[_];
IL void Prepare(){
isprime[1] = 1; phi[1] = 1;
for(RG int i = 2; i < _; ++i){
if(!isprime[i]){ prime[++num] = i; phi[i] = (i - 1); }
for(RG int j = 1; j <= num && i * prime[j] < _; ++j){
isprime[i * prime[j]] = 1;
if(i % prime[j]) phi[i * prime[j]] = 1LL * phi[i] * (prime[j] - 1) % Zsy;
else{ phi[i * prime[j]] = 1LL * phi[i] * prime[j] % Zsy; break; }
}
}
for(RG int i = 2; i < _; ++i) phi[i] = 1LL * phi[i] * i % Zsy, (phi[i] += phi[i - 1]) %= Zsy;
}
IL ll Sumphi(RG ll n){
if(n < _) return phi[n];
if(Phi[n]) return Phi[n];
RG ll ans = n * (n + 1) % Zsy * (2 * n + 1) % Zsy * yyb % Zsy;
for(RG ll i = 2, j; i <= n; i = j + 1){
j = n / (n / i);
ans -= 1LL * (j + i) * (j - i + 1) / 2 % Zsy * Sumphi(n / i) % Zsy;
ans = (ans + Zsy) % Zsy;
}
return Phi[n] = ans;
}
int main(RG int argc, RG char* argv[]){
Prepare(); RG ll n = Read();
printf("1\n%lld\n", Sumphi(n));
return 0;
}