建立网站线上营销,深圳公司注册服务,企业vis是指什么,做旅游网站需要什么problem
洛谷链接
solution
将 L,HL,HL,H 的范围放缩 1K\frac 1 KK1#xff0c;都除掉 KKK#xff0c;特殊的 LLL 边界注意一下。 H←H/K,L←(L−1)/K1H\leftarrow H/K,L\leftarrow (L-1)/K1H←H/K,L←(L−1)/K1。
问题转化为 [L,H][L,H][L,H] 中任选 NNN 个数 gcd1\te…problem
洛谷链接
solution
将 L,HL,HL,H 的范围放缩 1K\frac 1 KK1都除掉 KKK特殊的 LLL 边界注意一下。
H←H/K,L←(L−1)/K1H\leftarrow H/K,L\leftarrow (L-1)/K1H←H/K,L←(L−1)/K1。
问题转化为 [L,H][L,H][L,H] 中任选 NNN 个数 gcd1\text{gcd}1gcd1 的方案数。
T(i):T(i):T(i): 从 [L,H][L,H][L,H] 中选 NNN 个数 i∣gcdi|\text{gcd}i∣gcd 的方案数即 (⌊Hi⌋−⌊L−1i⌋)N(\lfloor\frac H i\rfloor-\lfloor\frac {L-1}i\rfloor)^N(⌊iH⌋−⌊iL−1⌋)N。
t(i):t(i):t(i): 从 [L,H][L,H][L,H] 中选 NNN 个数 igcdi\text{gcd}igcd 的方案数。
根据定义显然有T(i)∑i∣dt(d)T(i)\sum_{i|d}t(d)T(i)∑i∣dt(d)
莫比乌斯反演得 t(i)∑i∣dμ(di)T(d)t(i)\sum_{i|d}\mu(\frac{d}{i})T(d)t(i)∑i∣dμ(id)T(d)
答案即为 t(1)∑i1infμ(i)T(i)∑i1infμ(i)(⌊Hi⌋−⌊L−1i⌋)Nt(1)\sum_{i1}^{inf}\mu(i)T(i)\sum_{i1}^{inf}\mu(i)(\lfloor\frac H i\rfloor-\lfloor\frac {L-1}i\rfloor)^Nt(1)∑i1infμ(i)T(i)∑i1infμ(i)(⌊iH⌋−⌊iL−1⌋)N。
H,LH,LH,L 非常大不能直接线筛后整除分块。
但可杜教筛设定一个阀值 MMM 预处理出 MMM 以内的 μ\muμ同样整除分块后杜教筛能做到 O(H23)O(H^{\frac 2 3})O(H32)。
按 T(i)T(i)T(i) 分类假设 i∈[l,r]i\in[l,r]i∈[l,r] 的 T(i)T(i)T(i) 都是一样的那么对 ∑ilrμ(i)\sum_{il}^r\mu(i)∑ilrμ(i) 进行杜教筛迅速求和。
∑ilrμ(i)∑i1rμ(i)−∑i1l−1μ(i)\sum_{il}^r\mu(i)\sum_{i1}^r\mu(i)-\sum_{i1}^{l-1}\mu(i)∑ilrμ(i)∑i1rμ(i)−∑i1l−1μ(i)。这样就化成了标准的杜教筛形式。
∑μ(i):ϵμ∗I\sum\mu(i):\epsilon\mu*I∑μ(i):ϵμ∗I。h↔ϵ;f↔μ;g↔Ih\leftrightarrow \epsilon;f\leftrightarrow \mu;g\leftrightarrow Ih↔ϵ;f↔μ;g↔I。
s(n)∑i1nf(i)∑i1nμ(i)s(n)\sum_{i1}^nf(i)\sum_{i1}^n\mu(i)s(n)∑i1nf(i)∑i1nμ(i)
g(1)s(n)∑i1nϵ(i)−∑i2ng(i)s(⌊ni⌋)⇔s(n)1−∑i2ns(⌊ni⌋)g(1)s(n)\sum_{i1}^n\epsilon(i)-\sum_{i2}^ng(i)s(\lfloor\frac n i\rfloor)\Leftrightarrow s(n)1-\sum_{i2}^ns(\lfloor\frac n i\rfloor)g(1)s(n)∑i1nϵ(i)−∑i2ng(i)s(⌊in⌋)⇔s(n)1−∑i2ns(⌊in⌋)。
对 sss 函数进行记忆化递归以及同样的整除分块。
这样子连 H−L≤1e5H-L\le 1e5H−L≤1e5 的性质都没有用上^_^ 这性质好像是拿来容斥递推用的。
一些省掉的推导☞莫比乌斯反演杜教筛。
code
#include bits/stdc.h
using namespace std;
#define int long long
#define mod 1000000007
#define maxn 1000005
int mu[maxn], prime[maxn];
bool vis[maxn];
unordered_map int, int mp;
int N, M, K, L, H, cnt;int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}int solve( int n ) {if( n M ) return mu[n];if( mp.find( n ) ! mp.end() ) return mp[n];int ans 1;for( int l 2, r;l n;l r 1 ) {r n / ( n / l );( ans - solve( n / l ) * ( r - l 1 ) ) % mod;}return mp[n] ans;
}signed main() {scanf( %lld %lld %lld %lld, N, K, L, H );H / K, L ( L - 1 ) / K 1;M min( (int)1e6, H );mu[1] 1; for( int i 2;i M;i ) {if( ! vis[i] ) prime[ cnt] i, mu[i] -1;for( int j 1;j cnt and i * prime[j] M;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) { mu[i * prime[j]] 0; break; }else mu[i * prime[j]] -mu[i];}}for( int i 1;i M;i ) mu[i] mu[i - 1];L --; int ans 0;for( int l 1, r;l H;l r 1 ) {if( ! ( L / l ) ) r H / ( H / l );else r min( H / ( H / l ), L / ( L / l ) );( ans qkpow( H / l - L / l, N ) * ( solve( r ) - solve( l - 1 ) ) ) % mod;}printf( %lld\n, ( ans mod ) % mod );return 0;
}
