水题。过于屑。写来放松身心。
\[ \begin{align*} & \sum\limits_{1 \le i_1,i_2,\dots,i_n \le m} \gcd(i_1,i_2,\dots,i_n) \\ = & \sum\limits_{1 \le i_1,i_2,\dots,i_n \le m} \sum\limits_{d|\gcd(i_1,i_2,\dots,i_n)} \varphi(d) \\ = & \sum\limits_{d=1}^m \varphi(d)(\lfloor\frac md\rfloor)^n \end{align*} \]
然后随手一个杜教筛就没了。
注意 \(\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
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);
}