洛谷 2155[SDOI2008]沙拉公主的困惑 题解（数论）

原题链接： 洛谷:点我QωQ bzoj：点我QωQ （常数过不去。。。用另一种写法过的）

题意简述

给定$n,m$，保证$n>=m$，求$[1,n!]$中与$m!$互质的有多少。

数据

输入

一行两个正整数$n,m(n,m<=1e7)$。

输出

如题意简述

思路

我们会发现，对于一个数$p$，用一个$01$序列表示一个序列和$p$互质的情况，$0$表示不互质，$1$表示互质。那么，$[1,p]$的这个$01$序列和$[p+1,2p]$,$[2p+1,3p],\cdots [(n-1)p+1,np]$是一样的。

不信？我们试试。如$p=9$。那么，$[1,p]$的这个$01$序列应该等于 $110110110$ 会发现，$[p+1,2p]$的这个$01$序列也等于： $110110110$

所以，设$[1,p]$中和$p$互质的有$k$个，那么$[1,np]$中和$p$互质的就有$nk$个。回到这个题中，我们只要求出$[1,m!]$中多少个和$m!$互质，然后用它$\ast \frac{n!}{m!}$即珂。但是，如何求$[1,m!]$中多少个和$m!$互质(即$\varphi (m!)$)呢？

我们知道一个式子：$\varphi (x)=x\ast \prod _{i=1}^k\frac{p_i-1}{p_i}$，其中$p_1,p_2...p_k$是$x$的所有质因数。即$x$的$\varphi$值为：$x\ast \frac{x所有质因数-1}{x所有质因数}$。而$m!$的所有质因数就是$1m$中的所有质数。也就是说，我们的答案就是 $\frac{n!}{m!}\ast \prod _{i=1}^k\frac{p_k-1}{p_k}$。（其中$p_k$是$m$以内最大的质数）

所以，我们预处理好所有的质数，然后设$pre[i]$为前$i$个质数的$\frac{p-1}{p}$值之积（即前缀积）。每次询问的时候，$upper\_bound$一下$m$的位置，乘一下即珂。当然我们也要求出阶乘（也是前缀积的思想）。会发现，那个$pre$数组在算的时候要涉及到除法，两个阶乘也要除，那没问题，跑一下逆元就珂以了。

代码:

#include<bits/stdc++.h> using namespace std; namespace Flandle_Scarlet { #define N 10000005 #define int long long int t,r; int n,m; int primes[N];bool notp[N];//质数 int inv[N];//逆元 int fact[N];//阶乘 int pre[N];//前缀积 int qpow(int a,int b,int m)//快速幂 { int r=1; while(b) { if (b&1) r=r*a%m; a=a*a%m,b>>=1; } return r; } void Init()//O(n)=O(1e7) { int n=10000000; int& cnt=primes[0]; notp[1]=1; for(int i=2;i<=n;++i) { if (!notp[i]) { primes[++cnt]=i; } for(int j=1;j<=cnt and i*primes[j]<=n;++j) { int u=primes[j]; notp[i*u]=1; if (i%u==0) break; } }//处理质数 for(int i=1;i<=primes[0];++i) { inv[i]=qpow(primes[i],r-2,r); }//处理质数的逆元 fact[0]=1; for(int i=1;i<=n;++i) { fact[i]=fact[i-1]*i%r; }//处理阶乘 pre[0]=1; for(int i=1;i<=primes[0];++i) { int u=primes[i]; pre[i]=pre[i-1]*(u-1)%r*inv[i]%r; }//处理pre } void Solve() { int ans=fact[n]; int pos=upper_bound(primes+1,primes+primes[0]+1,m)-primes-1; //upper_bound之后-1是最后一个<=某个数的位置 //lower_bound是第一个<=某个数的位置，所以不能用lower_bound ans*=pre[pos];ans%=r; printf("%lld\n",ans); } void Main() { if (0) { freopen("","r",stdin); freopen("","w",stdout); } scanf("%lld%lld",&t,&r); Init(); while(t--) { scanf("%lld%lld",&n,&m); Solve(); } } #undef N //10000005 #undef int //long long }; main() { Flandle_Scarlet::Main(); return 0; }

回到总题解界面