题解 P1891 【疯狂 LCM】

$$ ans=\sum_{i=1}^nlcm(i,n) $$ $$ \begin{aligned} ans & =\sum_{i=1}^nlcm(i,n) \\ & =\sum_{i=1}^n\frac{i\cdot n}{gcd(i,n)} \\ & =n\times \sum_{i=1}^n\frac{i}{gcd(i,n)} \\ & =n\times\sum_{i=1}^ni\sum_{d=1}^i\frac{[gcd(i,n)=d]}{d} \\ & =n\times \sum_{d|n}\sum_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}i\cdot[gcd(i,\frac{n}{d})=1] \end{aligned} $$ 我们看后面的东西 ------------ 设 $$ g(n)=\sum_{i=1}^ni\cdot [gcd(i,n)=1] $$ 我们知道更相减损术 $$ gcd(a,b)=gcd(a,a-b) $$ 所以 $$ gcd(i,d)=1\Leftrightarrow gcd(d-i,d)=1 $$ 所以 对于每一个i，都有另一个d-i与其对应，而且两个数的和是个**定值**！ 所以 $$ g(n)=\frac{\varphi(n)}{2}\times d $$ 但是g(1)是个特例，所以要特别处理 g出来了之后我们再预处理答案，核心代码如下 ```cpp for (int i = 1; i <= N; i++) { for (int j = i; j <= N; j += i) { S[j] += (g[i] * i + 1) >> 1; } } ``` 这样就可以做到了。 ```cpp #include<cstdio> #define Starseven main #define ll long long namespace lyt { void read(int &x){ char ch=getchar();int re=0,op=1; while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();} while(ch>='0'&&ch<='9'){re=(re<<3)+(re<<1)+ch-'0';ch=getchar();} x = re * op; return ; } void read(long long &x){ char ch=getchar();long long re=0,op=1; while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();} while(ch>='0'&&ch<='9'){re=(re<<3ll)+(re<<1ll)+ch-'0';ch=getchar();} x = re * op; return ; } void write(int x){ if(x<0){putchar('-');x=-x;} if(x>9) write(x/10); putchar(x%10+'0'); return ; }//记得自己加空格和换行 void write(long long x){ if(x<0){putchar('-');x=-x;} if(x>9) write(x/10); putchar(x%10+'0'); return ; }//记得自己加空格和换行 int max(int x,int y){return x<y?y:x;} int min(int x,int y){return x<y?x:y;} int abs(int x){return x<0?-x:x;} long long max(long long x,long long y){return x<y?y:x;} long long min(long long x,long long y){return x<y?x:y;} long long abs(long long x){return x<0?-x:x;} double abs(double x){return x<0?-x:x;} void swap(int &a,int &b) {a ^= b ^= a ^= b;} void swap(long long &a,long long &b) {a ^= b ^= a ^= b;} }using namespace lyt; const int N = 1e6; int prime[N + 20], num; ll S[N + 20], g[N + 20]; bool vis[N + 20]; void Init(void) { g[1] = 1; for (int i = 2; i <= N; i++) { if(!vis[i]) { g[i] = i - 1; prime[++num] = i; } for (int j = 1; j <= num && prime[j] * i <= N; j++) { int x = prime[j] * i; vis[x] = true; if(i % prime[j] == 0) { g[x] = g[i] * prime[j]; break; } g[x] = g[i] * g[prime[j]]; } } return ; } int Starseven(void) { int t; read(t); Init(); for (int i = 1; i <= N; i++) { for (int j = i; j <= N; j += i) { S[j] += (g[i] * i + 1) >> 1;//我这里没有特判1，而是用了一点小技巧 } } while(t--) { int n; read(n); write(S[n] * n * 1ll); puts(""); } return 0; } ```