Tony102's Blog - 欧拉函数
type: channel
link: https://tony102.com/index.php/tag/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0/
items: Luogu1891 疯狂 LCM

Luogu1891 疯狂 LCM
type: item
date: 2020-11-24T21:11:00+08:00
description: LinkSol主要考察的是 $gcd$ 和 $lcm$ 关系的一个性质: $lcm(a, b) = \frac{a \times b}{gcd(a,b)}$那么我们用这个式子来替换现在的式子$$ \sum_{i=1}^{n} \frac{i \times n}{gcd(i,n)} $$把乘的 $n$ 这个常数项直接提到外面来,稍微改改$$ n \times \sum_{i=1}^{n} \frac{i}{gcd(i,n)} $$常见套路:有整除,gcd,约数的时候,把枚举的东西改成枚举约数,再改成枚举倍数那么我们先枚举约数试试$$ n \times \sum_{d|n} \sum_{i=1}^{n} \frac{i}{d} [gcd(i,n) = d] $$再把中括号(布尔表达式)内的东西同时除一个 $d$$$ n \times \sum_{d|n} \sum_{i=1}^{n} \frac{i}{d} [gcd(\frac{i}{d}, \frac{n}{d}) = 1] $$再写成枚举倍数的$$ n \times \sum_{d|n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} i [gcd(i,\frac{n}{d}) = 1] $$注意到因为 $d|n$,所以 $\frac{n}{d}$ 与 $d$ 等价,全部改成枚举到 $d$$$ n \times \sum_{d|n} \sum_{i=1}^{d} i [gcd(i,d) = 1] $$现在应该很显然, $[gcd(i,d)=1]$ 就是 $\varphi(d)$实际上因为 $n$ 的约数是成对出现的,那么一共会有 $\frac{d}{2}$ 对约数,直接把后面的东西利用这个性质算出来.所以现在就是$$ n \times \sum_{d|n} \frac{d}{2} \times \varphi(n) $$Code#include <bits/stdc++.h> using namespace std; #define int long long const int SIZE = 1e6 + 5; int T, n, tot; int prime[SIZE], phi[SIZE], isPrime[SIZE], ans[SIZE]; namespace ae86 { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (!isdigit(c))b ^= c == '-', c = fetch(); while (isdigit(c)) a = a * 10 + c - 48, c = fetch(); return b ? a : -a; } } using ae86::read; inline void euler() { int siz = 1e6 + 1; phi[1] = isPrime[1] = 1; for (register int i = 2; i <= siz; ++ i) { if (!isPrime[i]) { prime[++ tot] = i, phi[i] = i - 1; } for (register int j = 1; j <= tot && i * prime[j] <= siz; ++ j) { isPrime[i * prime[j]] = 1; if (i % prime[j]) phi[i * prime[j]] = phi[i] * phi[prime[j]]; else { phi[i * prime[j]] = phi[i] * prime[j]; break; } } } } signed main() { // freopen("code.in", "r", stdin); // freopen("code.out", "w", stdout); T = read(); euler(); int siz = 1e6 + 1; for (int i = 1; i <= siz; ++ i) { for(int j = 1; i * j <= siz; ++ j) ans[i * j] += (i == 1 ? 1 : 1ll * phi[i] * i / 2…

Luogu1891 疯狂 LCM
type: item
date: 2020-11-14T17:00:00+08:00
description: LinkSol主要考察的是 $gcd$ 和 $lcm$ 关系的一个性质: $lcm(a, b) = \frac{a \times b}{gcd(a,b)}$那么我们用这个式子来替换现在的式子$$\sum_{i=1}^{n} \frac{i \times n}{gcd(i,n)}$$把乘的 $n$ 这个常数项直接提到外面来,稍微改改$$n \times \sum_{i=1}^{n} \frac{i}{gcd(i,n)}$$常见套路:有整除,gcd,约数的时候,把枚举的东西改成枚举约数,再改成枚举倍数那么我们先枚举约数试试$$n \times \sum_{d|n} \sum_{i=1}^{n} \frac{i}{d} [gcd(i,n) = d]$$再把中括号(布尔表达式)内的东西同时除一个 $d$$$n \times \sum_{d|n} \sum_{i=1}^{n} \frac{i}{d} [gcd(\frac{i}{d}, \frac{n}{d}) = 1]$$再写成枚举倍数的$$n \times \sum_{d|n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} i [gcd(i,\frac{n}{d}) = 1]$$注意到因为 $d|n$,所以 $\frac{n}{d}$ 与 $d$ 等价,全部改成枚举到 $d$$$n \times \sum_{d|n} \sum_{i=1}^{d} i [gcd(i,d) = 1]$$现在应该很显然, $[gcd(i,d)=1]$ 就是 $\varphi(d)$实际上因为 $n$ 的约数是成对出现的,那么一共会有 $\frac{d}{2}$ 对约数,直接把后面的东西利用这个性质算出来.所以现在就是$$n \times \sum_{d|n} \frac{\varphi(d)}{2} \times d $$Code#include <bits/stdc++.h> using namespace std; #define int long long const int SIZE = 1e6 + 5; int T, n, tot; int prime[SIZE], phi[SIZE], isPrime[SIZE], ans[SIZE]; namespace ae86 { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (!isdigit(c))b ^= c == '-', c = fetch(); while (isdigit(c)) a = a * 10 + c - 48, c = fetch(); return b ? a : -a; } } using ae86::read; inline void euler() { int siz = 1e6 + 1; phi[1] = isPrime[1] = 1; for (register int i = 2; i <= siz; ++ i) { if (!isPrime[i]) { prime[++ tot] = i, phi[i] = i - 1; } for (register int j = 1; j <= tot && i * prime[j] <= siz; ++ j) { isPrime[i * prime[j]] = 1; if (i % prime[j]) phi[i * prime[j]] = phi[i] * phi[prime[j]]; else { phi[i * prime[j]] = phi[i] * prime[j]; break; } } } } signed main() { // freopen("code.in", "r", stdin); // freopen("code.out", "w", stdout); T = read(); euler(); int siz = 1e6 + 1; for (int i = 1; i <= siz; ++ i) { for(int j = 1; i * j <= siz; ++ j) ans[i * j] += (i == 1 ? 1 : 1ll * phi[i] * i / 2); } while (T…