题目

题目大意

求方程\((x^m-x)\mod n=0\)在整数范围\([1,n]\)的解的个数。

\(n=\sum_{i=1}^{c}p_i\)

给出\(c\)和\(p_i\)

思考历程

作为数论白痴，比赛时看到这题就想要自闭了……

乱推一波式子，后面的就不会搞了。

于是就想部分分……结果连部分分都没有想出来。

直接打了个\(20\)分的暴力。

正解

可以把方程拆成\(c\)个方程（对于每个\(i\)）：\((x^m-x)\mod p_i=0\)

分别解出每个同余方程组。解的时候枚举\(x\)，并将每个\(x^m\)处理出来。

快速幂会TLE，所以要用积性筛的方式来求\(x^m\)。具体来说，函数\(f(x)=x^m\)是个积性函数。所以用快速幂求出\(x\)为质数时的\(x^m\)，合数就是两个因数的函数值乘起来。

这样时间复杂度是可以过的。

处理出来之后，每个同余方程的解的个数的乘积就是整个同余方程组的解的个数。

证明；

对于方程\((x^m-x)\mod p_i=0\)，设解为\(x_{i,1},x_{i,2},...,x_{i,s_i}\)

每个方程分别抽出一个解来，记作\(x_i\)，\(x_i\)为\(x_{i,1..s_i}\)中的一个解。

设方程组的解为\(X\)

那么这个\(X\)满足以下方程组（对于每个\(i\)）：

\(X \equiv x_i (\mod p_i)\)

根据中国剩余定理，这个方程组只会有一个解。

方程组的解和\(x_1,x_2,..,x_c\)的取值是一一对应的（这个可以感性理解）。

对于\(x_i\)，有\(s_i\)种可能的取值。根据乘法原理，同余方程组解的个数即为每个同余方程的解的个数的乘积。

后来我知道了一个更加强大的方法。

同样是求\((x^m-x)\mod p_i=0\)的解的个数，然而这次不用暴力求。

有个性质：解的个数等于\(\gcd(m-1,p_i-1)+1\)

（为了方便，后面直接将\(p_i\)的下标省略。）

证明：

原式可以写成\(x^m\equiv x(\mod p)\)

\(p=2\)的时候显然成立。

\(x=0\)显然是方程的解

考虑解在区间\([1,p-1]\)的取值

由于\(p\)为奇素数，所以一定有原根。设原根为\(g\)

方程可以表示为\(g^{ym}\equiv g^y (\mod p)\)

由费马小定理得\(ym\equiv y (\mod (p-1))\)

也就是\(y(m-1) \equiv 0 (\mod (p-1))\)

设\(k=\gcd(m-1,p-1)\)。两边同时除以\(k\)得\(y\frac{m-1}{k}\equiv 0 (\mod \frac{p-1}{k})\)

由于\(\gcd(\frac{m-1}{k},\frac{p-1}{k})=1\)，所以\(\frac{p-1}{k}|y\)

所以\(y\)为\(\frac{p-1}{k}\)的倍数，显然可以取\(0\)到\(k-1\)倍，也就是说\(y\)有\(k\)个解。

所以\(x\)也有\(k\)个解。

所以解的个数为\(\gcd(m-1,p_i-1)+1\)

有了这条性质，程序就快得飞起了（爆踩标程）……

代码

暴力求解：

（反正数据范围这么小，就懒得打线筛了。埃氏筛法的常数小一些）

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#define mo 998244353

#define P 10000

int id;

int c,m;

int n;

inline int my_pow(int x,int y,int p){

	int res=1;

	for (;y && res;y>>=1,x=x*x%p)

		if (y&1)

			res=res*x%p;

	return res;

}

int di[P+1];

int xm[P+1];

inline void init(){

	di[1]=1;

	for (register int i=2;i<=P;++i){

		if (di[i])

			continue;

		di[i]=i;

		for (int j=i*i;j<=P;j+=i)

			di[j]=i;

	}

}

inline int work(int p){

	int res=2;

	xm[0]=0,xm[1]=1;

	for (register int i=2;i<=p;++i){

		xm[i]=(di[i]==i?my_pow(i,m,p):xm[i/di[i]]*xm[di[i]]%p);

		res+=(xm[i]==i);

	}

	return res;

}

int main(){

	freopen("division.in","r",stdin);

	freopen("division.out","w",stdout);

	int T;

	scanf("%d%d",&id,&T);

	init();

	while (T--){

		scanf("%d%d",&c,&m);

		long long ans=1;

		for (int i=1;i<=c;++i){

			int p;

			scanf("%d",&p);

			ans=ans*work(p)%mo;

		}

		printf("%lld\n",ans);

	}

	return 0;

}

牛逼解法：

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#define mo 998244353

inline int gcd(int a,int b){

	int k;

	while (b){

		k=a%b;

		a=b;

		b=k;

	}

	return a;

}

int main(){

	freopen("division.in","r",stdin);

	freopen("division.out","w",stdout);

	int T;

	scanf("%*d%d",&T);

	while (T--){

		int c,m;

		scanf("%d%d",&c,&m);

		long long ans=1;

		while (c--){

			int p;

			scanf("%d",&p);

			ans=ans*(gcd(p-1,m-1)+1)%mo;

		}

		printf("%lld\n",ans);

	}

	return 0;

}

总结

看来我的数论还是太菜了……QWQ……

巴特西

[JZOJ6272] 2019.8.4【NOIP提高组A】整除

题目

题目大意

思考历程

正解

代码

总结

最新文章

热门文章