poj3243 Clever Y

poj3243 Clever Y

​​ Description

Little Y finds there is a very interesting formula in mathematics:

XY mod Z = K

Given X, Y, Z, we all know how to figure out K fast. However, given X, Z, K, could you figure out Y fast?

Input

Input data consists of no more than 20 test cases. For each test case, there would be only one line containing 3 integers X, Z, K (0 ≤ X, Z, K ≤ 109). Input file ends with 3 zeros separated by spaces. Output

For each test case output one line. Write “No Solution” (without quotes) if you cannot find a feasible Y (0 ≤ Y < Z). Otherwise output the minimum Y you find. Sample Input

5 58 33 2 4 3 0 0 0 Sample Output

9 No Solution Source

POJ Monthly–2007.07.08, Guo, Huayang 别人再明白讲的再清楚也要自己推导明白才好。不能因为自己智商低为借口抄代码 考虑到一般的bsgs我们都会了（其实blog主是最辣鸡的！ 考虑做题遇到的最多的限制条件是什么 是p为质数 那么为什么这么做呢因为保证有逆元如果没有呢 没有这个条件满足ax≡b(modp) a x ≡ b ( m o d p ) 只要gcd(a,p)=1 直接做也是即可的只不过枚举只需要枚举0~φ(p)−1 φ ( p ) − 1 即可 那加入这两个条件均不满足怎么办那先把原始式转化一下比如a,p共同有一个公因子g 那么我可以用将原式替换一下 设A*d=a那么其他元素同理可以写成 A∗g∗ax−1≡B∗g(mod C∗g) A ∗ g ∗ a x − 1 ≡ B ∗ g ( m o d   C ∗ g ) 那么两边同时去掉一个g 即可变成A∗ax−1≡B(mod C) A ∗ a x − 1 ≡ B ( m o d   C ) 那么很好一直这样递归做下去知道a与C互质 同时记录一下一个nm表示我用掉了几个a 然后将前面的A用一个变量类乘起来辣鸡博主用mul 然后 一直到最后一定有个终止状态即g=1 最后的方程可以写成mul∗ax−nm≡b(mod c) m u l ∗ a x − n m ≡ b ( m o d   c )

#include#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}const int md=1e5+3;struct node{int x,id,next;}hs[md];int h[md],num;inline void init(){num=0;memset(h,0,sizeof(h));}inline void insert1(int x,int id){static int tmp;tmp=x%md; for (int i=h[tmp];i;i=hs[i].next) if (hs[i].x==x) return; hs[++num]=(node){x,id,h[tmp]};h[tmp]=num;}inline int query(int x){static int tmp;tmp=x%md; for (int i=h[tmp];i;i=hs[i].next) if (hs[i].x==x) return hs[i].id; return -1;}inline int gcd(int x,int y){return y?gcd(y,x%y):x;}inline int phi(int x){ if (x==1) return 1;int tmp=x; for (int i=2;i*i<=x;++i){ if (x%i) continue;tmp-=tmp/i; while(x%i==0) x/=i; }if(x>1) tmp-=tmp/x;return tmp;}inline int ksm(ll b,int t,int p){static ll tmp;tmp=1; for (;t;(b*=b)%=p,t>>=1) if(t&1) (tmp*=b)%=p;return tmp;}inline int exbsgs(int a,int b,int mod){static ll mul,tmp;static int nm,inva; if (!a) return !b?0:-1;ll aa=1; for (int i=0;i<=30;++i) {if (aa==b) return i;aa*=a;} int g=gcd(a,mod);mul=1;nm=0; while(g!=1){ if (b%g) return -1;(mul*=a/g)%=mod;++nm; b/=g;mod/=g;g=gcd(a,mod); }init();static ll tmp1;int m=ceil(sqrt(mod));tmp=b; tmp1=ksm(a,m,mod);inva=ksm(a,phi(mod)-1,mod); for (int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。