先来考虑在什么情况下存在一个x使得$ax equiv b (bmod m)$.
首先,如果a与m互质,那么一定存在一个x满足条件无疑.
如果a与m不互质,因为当$k|m$,$k|a$且$k|b$有$frac{a}{k}x equiv frac{b}{k} (bmod frac{m}{k})$成立.而且只有当$k=gcd(a,m)$时,存在逆元.因此如果$gcd(a,m)|gcd(b,m)$,则存在一个解.
因此DP处理出应该选哪些k作为gcd,然后用exgcd来进行转移即可.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
|
#define N 200010 #define ll long long using namespace std; int (int a,int b){ return b==0?a:gcd(b,a%b); } void exgcd(ll a,ll b,ll &x,ll &y){ if(b==0){ x=1;y=0; return; } exgcd(b,a%b,x,y); ll t=x;x=y;y=t-a/b*y; } int n,m; int vis[N],g[N],c[N],p[N]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); vis[x]=1; } for(int i=1;i<m;i++){ g[i]=gcd(i,m); if(vis[i]==0) c[g[i]]++; } for(int i=m-1;i>=1;i--){ for(int j=i+i;j<m;j+=i){ if(c[j]>c[p[i]]) p[i]=j; } c[i]+=c[p[i]]; } if(vis[0]==0) c[1]++; printf("%dn",c[1]); ll a=1,pre=1;; for(int k=1;k;k=p[k]){ for(int i=1;i<m;i++){ if(g[i]==k&&vis[i]==0){ ll x,y; exgcd(a,m,x,y); x=(x%m+m)%m; x=(x*i/pre)%m; pre=k; a=a*x%m; printf("%lld ",x); } } } if(vis[0]==0) printf("0n"); return 0; }
|
近期评论