欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

WC2020 猜数游戏

程序员文章站 2022-04-01 10:28:52
题目描述LOJ3330题目分析若存在 kkk 使得 ak≡b(modp)a^k\equiv b\pmod pak≡b(modp),则 aaa 向 bbb 连一条边。那么一个点在一个集合里面要被选的条件就是集合中不存在另一个点能够到达它(把环缩成点,每个环要被选的方案数是 2环大小−12^{环大小}-12环大小−1),那么所有方案选择的点数之和就是 ∑某个环2n−(可到达这个环的点数)∗(2环大小−1)\sum_{某个环} 2^{n-(可到达这个环的点数)}*(2^{环大小}-1)∑某个环​2n−(可...

题目描述

LOJ3330

题目分析

若存在 kk 使得 akb(modp)a^k\equiv b\pmod p,则 aabb 连一条边。

那么一个点在一个集合里面要被选的条件就是集合中不存在另一个点能够到达它(把环缩成点,每个环要被选的方案数是 212^{环大小}-1),那么所有方案选择的点数之和就是 2n()(21)\sum_{某个环} 2^{n-(可到达这个环的点数)}*(2^{环大小}-1)

暴力连边是 O(np)O(np) 的,容易想到用原根优化。

如果 pp 是奇素数,那么存在 kk 使得 gakgb(modp)g^{ak}\equiv g^b\pmod p 等价于存在 kk 使得 akb(modφ(p))ak\equiv b\pmod {\varphi(p)},即 gcd(a,φ(p))  bgcd(a,\varphi(p))~|~b
用 BSGS 求指标,复杂度就是 O(np+n2)O(n\sqrt p+n^2)

p=qkp=q^k 时,对于 (a,q)=1(a,q)=1 的可以按上面的方法做,而对于 aqbaq^b,它们的连边形成了一个 DAG,自乘 log 次后就会变成 0,不会成环,可以直接暴力做,复杂度 O(nlogp)O(n\log p)

pp为奇素数的算法还可以进一步优化,条件可以转化为 gcd(x,φ(p))  gcd(y,φ(p))gcd(x,\varphi(p))~|~gcd(y,\varphi(p)),而对于 gxag^x\equiv a,有 ord(a)=φ(p)gcd(x,φ(p))\text{ord}(a)=\frac {\varphi(p)}{gcd(x,\varphi(p))}ord(a)\text{ord(a)}aa 的阶,即使得 ak1(modp)a^k\equiv 1\pmod p 的最小的 kk,即使得 xk0(modφ(p))xk\equiv 0\pmod {\varphi(p)} 的最小的 kk

于是只需要求出 ord(a)\text{ord}(a) 即可,因为 ord(a)  φ(p)\text{ord}(a)~|~\varphi(p),可以用后者的质因子试除,复杂度 O(nlog2p)O(n\log^2p)

Code:

#include<bits/stdc++.h>
#define maxn 5005
using namespace std;
const int mod = 998244353;
int n,p,q,phi,d[35],pw[maxn],ans;
int v1[maxn],s1,v2[maxn],s2,cnt[maxn];
map<int,int>id1,id2;
void Divide(){
	for(int i=2;i*i<=q;i++) if(q%i==0) {p=i;break;}
	if(!p) p=q;
	int x=phi=q-q/p;
	for(int i=2;i*i<=x;i++) if(x%i==0) {d[++*d]=i; while(x%i==0) x/=i;}
	if(x>1) d[++*d]=x;
}
int Pow(int a,int b,int mod){int s=1;for(;b;b>>=1,a=1ll*a*a%mod) b&1&&(s=1ll*s*a%mod);return s;}
int ord(int x){
	int w=phi;
	for(int i=1;i<=*d;i++)
		while(w%d[i]==0&&Pow(x,w/d[i],q)==1) w/=d[i];
	return w;
}
int main()
{
	scanf("%d%d",&n,&q),Divide();
	for(int i=pw[0]=1;i<=n;i++) pw[i]=pw[i-1]*2%mod;
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		if(x%p==0) v2[++s2]=x,id2[x]=s2;
		else{
			x=ord(x);
			if(!id1[x]) id1[x]=++s1,v1[s1]=x;
			cnt[id1[x]]++;
		}
	}
	for(int i=1;i<=s1;i++){
		int sum=n;
		for(int j=1;j<=s1;j++) if(v1[j]%v1[i]==0) sum-=cnt[j];
		ans=(ans+1ll*pw[sum]*(pw[cnt[i]]-1))%mod;
	}
	for(int i=1;i<=s2;i++) cnt[i]=n;
	for(int i=1;i<=s2;i++)
		for(int x=v2[i];x;x=1ll*x*v2[i]%q)
			cnt[id2[x]]--;
	for(int i=1;i<=s2;i++) ans=(ans+pw[cnt[i]])%mod;
	printf("%d\n",ans);
}

本文地址:https://blog.csdn.net/C20181220_xiang_m_y/article/details/107885141

相关标签: 数论