LibreOJ 6491.「XXOI 2018」简单的最大公约数

水题。过于屑。写来放松身心。

然后随手一个杜教筛就没了。
注意 n(n+1)2\frac {n(n+1)}2 可能会炸,正确操作是先除以二再乘。

代码:

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 <cstdio>
#include <cstring>
using namespace std;
const unsigned long long N = 1e11;
const unsigned long long M = 1e11;
const int MX = 1e7;
unsigned long long n,m,ans;
inline unsigned long long fpow(unsigned long long a,unsigned long long b)
{
unsigned long long ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret *= a),a *= a;
return ret;
}
int vis[MX + 5],cnt,prime[MX + 5];
unsigned long long phi[MX + 5];
unsigned long long mem[MX + 5];
inline int id(unsigned long long x)
{
return n / x;
}
unsigned long long calc(unsigned long long n)
{
if(n <= MX)
return phi[n];
if(~mem[id(n)])
return mem[id(n)];
unsigned long long ret = (n & 1) ? ((n + 1 >> 1) * n) : ((n >> 1) * (n + 1));
for(register unsigned long long l = 2,r;l <= n;l = r + 1)
{
r = n / (n / l);
ret -= (r - l + 1) * calc(n / l);
}
return mem[id(n)] = ret;
}
int main()
{
memset(mem,-1,sizeof mem),phi[1] = 1;
for(register int i = 2;i <= MX;++i)
{
if(!vis[i])
phi[prime[++cnt] = i] = i - 1;
for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
phi[i] += phi[i - 1];
}
scanf("%llu%llu",&n,&m);
for(register unsigned long long l = 1,r;l <= m;l = r + 1)
{
r = m / (m / l);
ans += (calc(r) - calc(l - 1)) * fpow(m / l,n);
}
printf("%llu\n",ans);
}