Codeforce 1359 E. Modular Stability 解析(思維、數論、組合)

今天我們來看看CF1359E
題目連結

題目
略，請直接看原題。

前言

b

想法

首先我們觀察$k=2$的情況，因為總感覺只要兩個數字的情況明瞭了，應該不難推廣到$k$個數字的情況。
W.L.O.G. 假設$1\le a_1<a_2\le n$，那麼我們會有以下的式子：$\forall x\in\mathbb{N}_{\ge0}, (x%a_1)%a_2=x%a_1\textbf{=}(x%a_2)%a_1$，也就是說$x=u\cdot a_1+(x%a_1)=y\cdot a_2+r\cdot a_1+(x%a_1)$($u,y,r$是一些數字)。
我們猜想$a_1|a_2$，要證明這件事，首先假設$a_1\not|a_2$。並且由於$x$是任意非負整數，我們可以取$x$使得$x%a_1=0$，也就是說$x=u\cdot a_1=y\cdot a_2+r\cdot a_1$，並且$r\cdot a_1<a_2$。然而由於$x$是任意的非負整數，$u$也就是任意的非負整數，所以說我們可以取$u$使得$u\cdot a_1=y\cdot a_2+r\cdot a_1$並且$(u+1)\cdot a_1=(y+1)\cdot a_2+r’\cdot a_1$，兩式相減得到$(1-(r-r’))a_1=a_2$，然而$r,r’\in\mathbb{N}$，因此和假設相矛盾，定理得證，$a_1|a_2$。
那麼接下來證明，假設$a_1$是裡面最小的數字，$a_1|a_i\forall i\iff符合條件$。
$(\Rightarrow):$由於對於任何的取模排列，我們總是可以先對$a_1$取模(用到上面證明的$k=2$的情況)，因此得證。
$(\Leftarrow):$假設$a_1\not|a_j$對於某個$j$，那麼$x%a_1%a_j%…\neq x%a_j%a_1%…$對於某個$x$。

因此我們只要先決定了$a_1$，接下來的數字都會是$a_1$的倍數，用組合數計算可能性即可。

程式碼:

const int _n=5e5+10;  
int t,n,k,fac[_n],inv[_n];;  
ll ans;  
int C(int m,int n){  
  if(m<n)return 0;  
  if(m<mod and n<mod)return 1ll*fac[m]*inv[n]%mod*inv[m-n]%mod;  
  return 1ll*C(m/mod,n/mod)*C(m%mod,n%mod)%mod;  
}  
void genInv(){  
  fac[0]=1;rep(i,1,n+1)fac[i]=1ll*fac[i-1]*i%mod;=  
  inv[n]=powmod(fac[n],mod-2);per(i,0,n)inv[i]=1ll*inv[i+1]*(i+1)%mod;  
}  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>k;genInv();rep(i,1,n/k+1)ans=(ans+1ll*C(n/i-1,k-1))%mod;  
  cout<<ans<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission