bzoj 2186 [Sdoi2008]沙拉公主的困惑 歐拉函數

bzoj 2186 [Sdoi2008]沙拉公主的困惑 歐拉函數

bzoj 2186 [Sdoi2008]沙拉公主的困惑

題意：
大富翁國因為通貨膨脹，以及假鈔泛濫，政府決定推出一項新的政策：現有鈔票編號范圍為1到N的階乘，但是，政府只發行編號與M!互質的鈔票。房地產第一大戶沙拉公主決定預測一下大富翁國現在所有真鈔票的數量。現在，請你幫助沙拉公主解決這個問題，由於可能張數非常大，你只需計算出對R取模後的答案即可。R是一個質數。

限制：
數據組數T：1 <= T <= 10000
R <= 1e9+10
1 <= N,M <=10000000

思路：
首先答案為：
phi(m!)*n!/m!
證明過程如下：
gcd(a,b)=1 <=> gcd(a+b,b)=1
phi(m!)表示小於m!且與m!互質的數的個數，
不妨令它們為p[1],p[2],p[3],...,p[k]，則有gcd(p[i],m!)=1，其中1 <= i <= k，
則有gcd(p[i]+m!,m!)=1，
所以最後答案為phi(m!)*n!/m!


然後問題落在phi(m!)的求法上面，
對於歐拉函數有公式：
phi(x)=x * (p[1] - 1)/p[1] * (p[2] - 1)/p[2] * ... * (p[k] - 1)/p[k]，其中p[i] (1 <= i <= k) 為x的質因子
所以，求一遍m!的質因子即可，即為1~m內的素數。

/*bzoj 2186 [Sdoi2008]沙拉公主的困惑
  題意：
  大富翁國因為通貨膨脹，以及假鈔泛濫，政府決定推出一項新的政策：現有鈔票編號范圍為1到N的階乘，但是，政府只發行編號與M!互質的鈔票。房地產第一大戶沙拉公主決定預測一下大富翁國現在所有真鈔票的數量。現在，請你幫助沙拉公主解決這個問題，由於可能張數非常大，你只需計算出對R取模後的答案即可。R是一個質數。
  限制：
  數據組數T：1 <= T <= 10000
  R <= 1e9+10
  1 <= N,M <=10000000
  思路：
  首先答案為：
  phi(m!)*n!/m!
  證明過程如下：
  gcd(a,b)=1 <=> gcd(a+b,b)=1
  phi(m!)表示小於m!且與m!互質的數的個數，
  不妨令它們為p[1],p[2],p[3],...,p[k]，則有gcd(p[i],m!)=1，其中1 <= i <= k，
  則有gcd(p[i]+m!,m!)=1，
  所以最後答案為phi(m!)*n!/m!

  然後問題落在phi(m!)的求法上面，
  對於歐拉函數有公式：
  phi(x)=x * (p[1] - 1)/p[1] * (p[2] - 1)/p[2] * ... * (p[k] - 1)/p[k]，其中p[i] (1 <= i <= k) 為x的質因子
  所以，求一遍m!的質因子即可，即為1~m內的素數。
 */
#include
#include
#include
using namespace std;
#define LL long long
const int N=1e7+5;
LL fac[N];

LL ext_gcd(LL a,LL b,LL &x,LL &y){
    if(b==0) { x=1, y=0; return a; }
    LL ret= ext_gcd(b,a%b,y,x);
    y-= a/b*x;
    return ret;
}

//要求a與m互質
LL inv(LL a,int m){   //求逆元
    LL d,x,y,t= (LL)m;
    d= ext_gcd(a,t,x,y);
    if(d==1) return (x%t+t)%t;
    return -1;
}

bool is_pri[N];
//int pri[N], tot;
void get_pri(int n){
	//tot = 0;
	memset(is_pri, 1, sizeof(is_pri));
	is_pri[0] = is_pri[1] = 0;
	for(int i = 2; i <= n; ++i)
		if(is_pri[i]){
			if(n / i < i) break;
			for(int j = i * i; j <= n; j += i) is_pri[j] = false;
		}
	//for(int i = 2; i <= n; ++i) if(is_pri[i]) pri[tot++] = i;
}

LL ans[N];

void predo(int mod){
	fac[0]=1;
	for(int i=1;i