题意：求\(\frac{1}{n} \sum_{i=1}^n lcm(n,i)\)
和的弱化版？
\[ ans = \frac{1}{2}((\sum_{i=1}^n \sum_{d=1}^{\lfloor \frac{n}{i} \rfloor} d\cdot \varphi(d) ) - \sum_{i=1}^n) \] 求\(id\cdot \varphi\)的前缀和，卷上\(id\)就行了我竟然把整除分块打错了，直接i++，gg
#include#include #include #include #include using namespace std;typedef long long ll;const int N=1664512, U=1664510, mo=1e9+7, inv2 = 500000004, inv6 = 166666668;inline int read(){ char c=getchar(); int x=0,f=1; while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}inline void mod(int &x) {if(x>=mo) x-=mo; else if(x<0) x+=mo;}bool notp[N]; int p[N/10], phi[N], s[N];void sieve(int n) { phi[1]=1; s[1]=1; for(int i=2; i<=n; i++) { if(!notp[i]) p[++p[0]] = i, phi[i] = i-1; for(int j=1; j <= p[0] && i*p[j] <= n; j++) { notp[i*p[j]] = 1; if(i%p[j] == 0) {phi[i*p[j]] = (ll) phi[i] * p[j] %mo; break;} phi[i*p[j]] = (ll) phi[i] * (p[j]-1) %mo; } mod(s[i] += s[i-1] + (ll) phi[i] * i %mo); }}namespace ha { const int p=1001001; struct meow{int ne, val, r;} e[3000]; int cnt, h[p]; inline void insert(int x, int val) { int u = x%p; for(int i=h[u];i;i=e[i].ne) if(e[i].r == x) return; e[++cnt] = (meow){h[u], val, x}; h[u] = cnt; } inline int quer(int x) { int u = x%p; for(int i=h[u];i;i=e[i].ne) if(e[i].r == x) return e[i].val; return -1; }} using ha::insert; using ha::quer;inline ll sum(ll n) {return n * (n+1) / 2 %mo;}inline ll sum2(ll n) {return n * (n+1) %mo * (2*n+1) %mo *inv6 %mo;}int dj_s(int n) { //printf("dj_s %d\n", n); if(n <= U) return s[n]; if(quer(n) != -1) return quer(n); int ans = sum2(n), r; for(int i=2; i<=n; i=r+1) { r = n/(n/i); mod(ans -= (ll) (sum(r) - sum(i-1)) * dj_s(n/i) %mo); } insert(n, ans); return ans;}int solve(int n) { int ans=0, r; for(int i=1; i<=n; i=r+1) { r = n/(n/i); mod(ans += (ll) dj_s(n/i) * (r-i+1) %mo); } mod(ans += n); return (ll) ans * inv2 %mo;}int l, r;int main() { freopen("in", "r", stdin); sieve(U); l=read(); r=read(); int ans = solve(r) - solve(l-1); mod(ans); printf("%d", ans);}