苏州网站建设案例,化妆品的网站布局设计图片大全,wordpress php 并发,四川省建设厅官方网站上面查题目的意思大概是求1~N!中和M#xff01;互质的数的个数
因为对欧拉函数理解不够深刻所以我是分析得到结果的#xff1a;
当NM的时候显然符合要求的数的个数为0#xff1b;
当NM的时候我们要求的是1~N!中不含1 ~M的素因子的的数的个数#xff0c;结合欧拉函数的…题目的意思大概是求1~N!中和M互质的数的个数
因为对欧拉函数理解不够深刻所以我是分析得到结果的
当NM的时候显然符合要求的数的个数为0
当NM的时候我们要求的是1~N!中不含1 ~M的素因子的的数的个数结合欧拉函数的推导过程容斥原理假设N!在1 ~ M中含有k个素因子设nN!那么符合要求的数的个数就是
n−n/p1−n/p2−...−n/pkn/p1p2n/p1p3...n/p(k−1)pk−...n(1−1/p1)(1−1/p2)...(1−1/pk)n-n/p1-n/p2-...-n/pkn/p1p2n/p1p3...n/p(k-1)pk-...n(1-1/p1)(1-1/p2)...(1-1/pk)n−n/p1−n/p2−...−n/pkn/p1p2n/p1p3...n/p(k−1)pk−...n(1−1/p1)(1−1/p2)...(1−1/pk) 因为我们不能首先求出n的大小再算如果可以求出n的大小的话那显然直接计算就可以但是我们必须要模R在模R的情况下我们应该求出pi的逆元所以整个过程就是线性筛得到1~M的素数因子以及他们的逆元然后与N!相乘计算按照上面的公式
我的代码
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includectime
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e75;
int prime[MAXN];
bool check[MAXN];
int N[MAXN],r[MAXN],ans[MAXN];
int tot;
ll R,n,m;void ex_gcd(int a,int b,int d,int x,int y)
{if(!b) {da; x1; y0;}else{ex_gcd(b,a%b,d,y,x); y-(a/b)*x;}
}int getine(int a)
{int x,y,d;ex_gcd(a,R,d,x,y); x(x%RR)%R;return x;
}void creat_prime()
{tot0; r[1]1; N[1]1;for(int i2;iMAXN;i){N[i](ll)N[i-1]*i%R;if(!check[i]){prime[tot]i;r[i]getine(i);}for(int j0;jtot prime[j]*iMAXN;j){check[prime[j]*i]true;if(i%prime[j]0) break;}}
}void init()
{ans[1]1;for(int i2;iMAXN;i){ans[i]ans[i-1];if(!check[i]) ans[i](ll)ans[i]*(i-1)%R*r[i]%R;}
}int main()
{int T;scanf(%d%d,T,R);creat_prime();init();while(T--){scanf(%d%d,n,m);printf(%d\n,(ll)N[n]*ans[m]%R);}return 0;
}虽然可以得到正确的答案但是经过了自己的推导分析思维质量比较低。根本原因还是对欧拉函数的理解不够深刻。
让我们再来看看欧拉函数的意义求出1~n中和n互质的数的个数那么1 ~kn中与n互质的数的个数有多少呢答案是k*phi[n]结合上面推导也可以发现这个。为什么是这样呢
互质即意味着gcd(x,n)1gcd(x,n)1gcd(x,n)1由最大公约数的性质我们得到gcd(xkn,n)1gcd(xkn,n)1gcd(xkn,n)1即这个数在每次kn1~(k1)n中都会出现一次所以答案是k*phi[n]
回到这个问题题目要求1~N!中和M!互质的数的个数那么答案应该是N!/M!*phi[M!]再结合欧拉函数值的求法可以得到上面的过程。
学习了一下递推法求逆元.(递推法求逆元如果不是都要用时间还是慢一点)
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includectime
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e75;
int prime[MAXN];
bool check[MAXN];
int N[MAXN],r[MAXN],ans[MAXN];
int tot;
ll R,n,m;int read()
{int x0;char chgetchar();while(ch0||ch9)chgetchar();while(ch0ch9){xx*10ch-0;chgetchar();}return x;
}void ex_gcd(int a,int b,int d,int x,int y)
{if(!b) {da; x1; y0;}else{ex_gcd(b,a%b,d,y,x); y-(a/b)*x;}
}int getine(int a)
{int x,y,d;ex_gcd(a,R,d,x,y); x(x%RR)%R;return x;
}void creat_prime()
{tot0; r[1]1; N[1]1;for(int i2;iMAXN;i){N[i](ll)N[i-1]*i%R;if(!check[i]){prime[tot]i;//r[i]getine(i);}for(int j0;jtot prime[j]*iMAXN;j){check[prime[j]*i]true;if(i%prime[j]0) break;}}for(int i2;iMAXNiR;i)r[i]R-(ll)R/i*r[R%i]%R;
}void init()
{ans[1]1;for(int i2;iMAXN;i){ans[i]ans[i-1];if(!check[i]) ans[i](ll)ans[i]*(i-1)%R*r[i]%R;}
}int main()
{int T;Tread(); Rread();creat_prime();init();while(T--){nread(); mread();printf(%d\n,(ll)N[n]*ans[m]%R);}return 0;
}
