![\"\[X_{i+1} \equiv a*X_{i}+b\ (mod\ p)\]\"](\"https:\/\/nocriz.com\/wp-content\/ql-cache\/quicklatex.com-0ff1495f3708fb3f774ed02d6accb523_l3.png\" "\\"Rendered")
<\/p><\/p>\n\n\n\n <\/span> <\/span> \u8fd9\u9053\u9898\u4e5f\u662f\u4e00\u9053BSGS\u3002<\/p>\n\n\n\n\n\n\n\n \u00a0\u4e0d\u96be\u63a8\u51fa<\/p>\n\n\n\n <\/span> <\/span> <\/span> <\/span> \u90a3\u4e48\u53ea\u8981\u6c42\u6ee1\u8db3<\/p>\n\n\n\n <\/span> <\/span> \u7684\u6700\u5c0fx\u5373\u53ef\uff0c\u8fd9\u4e00\u6b65\u53ef\u4ee5\u4f7f\u7528BSGS\u89e3\u51b3\u3002\u8fd9\u9053\u9898\u8fd8\u6709\u4e00\u4e9b\u7279\u5224\uff0c\u6bd4\u8f83\u7e41\u3002\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n \u8fd9\u9053\u9898\u4e5f\u662f\u4e00\u9053BSGS\u3002<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,5],"tags":[7],"_links":{"self":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/226"}],"collection":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=226"}],"version-history":[{"count":1,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/226\/revisions"}],"predecessor-version":[{"id":752,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/226\/revisions\/752"}],"wp:attachment":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=226"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=226"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=226"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"\[给出a,b,X_1,求满足X_{i} = t的最小i\]\"](\"https:\/\/nocriz.com\/wp-content\/ql-cache\/quicklatex.com-2f213f3f1ff39dd29976fbc69519dd52_l3.png\" "\\"Rendered")
<\/p><\/p>\n\n\n\n![\"\[X_{i+1} +\frac{b}{a-1} \equiv a*(X_{i}+\frac{b}{a-1})\ (mod\ p)\]\"](\"https:\/\/nocriz.com\/wp-content\/ql-cache\/quicklatex.com-4977519277784e3c80e339a3aec4acf7_l3.png\" "\\"Rendered")
<\/p><\/p>\n\n\n\n![\"\[X_{n} +\frac{b}{a-1} \equiv a^{n-1}*(X_1+\frac{b}{a-1})\ (mod\ p)\]\"](\"https:\/\/nocriz.com\/wp-content\/ql-cache\/quicklatex.com-6b705c03d8b5f6e4ba9cfeaf94c9cab8_l3.png\" "\\"Rendered")
<\/p><\/p>\n\n\n\n![\"\[a^x \equiv \frac{(a-1)t+b}{(a-1)X_1+b}\ (mod\ p)\]\"](\"https:\/\/nocriz.com\/wp-content\/ql-cache\/quicklatex.com-c9990126e04a67c9c952aba96910931c_l3.png\" "\\"Rendered")
<\/p><\/p>\n\n\n\n#include <cmath>\n#include <cstdio>\n#include <cstring>\n#include <iostream>\n#include <algorithm>\n#include <unordered_map>\nusing namespace std;\ntypedef long long ll;\ntemplate<typename T> void read(T &x){\n\tx = 0;char ch = getchar();\n\twhile(!isdigit(ch))ch=getchar();\n\twhile(isdigit(ch)){x = x*10+ch-48;ch=getchar();}\n}\nint mod,y,z,blc;\nint mul(int a,int b){return 1ll*a*b%mod;}\nint sq(int x){return 1ll*x*x%mod;}\nint mpow(int a,int b){if(b == 0)return 1;return b&1?mul(a,sq(mpow(a,b\/2))):sq(mpow(a,b\/2));}\nint inv(int x){return mpow(x,mod-2);}\nint exgcd(int a,int b,int &x,int &y){\n\tif(b==0){x=1;y=0;return a;}\n\tint d=exgcd(b,a%b,y,x);y-=1ll*a\/b*x;return d;\n}\nunordered_map<int,int> ump;\nint main() {\n\tint TT,a,b,x1,t;\n\tread(TT);\n\twhile(TT--){\n\t\tread(mod);read(a);read(b);read(x1);read(t);\n\t\ty = a%mod;\n\t\tif(x1 == t){cout<<\"1\\n\";continue;}\n\t\tif(a==0){\n\t\t\tif(b==t)cout<<\"2\\n\";\n\t\t\telse cout<<\"-1\\n\";\n\t\t\tcontinue;\n\t\t}\n\t\tif(a == 1){\n\t\t\tint c = (t-x1+mod)%mod,x,y;\n\t\t\tint d = exgcd(b,mod,x,y);\n\t\t\tif(c%d!=0)cout<<\"-1\\n\";\n\t\t\telse{\n\t\t\t\tx=1ll*x*c\/d%mod;if(x<0)x+=mod;\n\t\t\t\tcout<<x+1<<endl;\n\t\t\t}\n\t\t\tcontinue;\n\t\t}\n\t\tz = mul(mul(a-1,t)+b,inv(mul(a-1,x1)+b));\n\t\tump.clear();\n\t\tblc = sqrt(mod)+1;\n\t\tint cc = 1;\n\t\tfor(int i=0;i<blc;i++){\n\t\t\tif(!ump.count(cc))ump[cc] = i;\n\t\t\tcc = mul(cc,y);\n\t\t}\n\t\tint st = 1,stinv = 1,invcc = inv(cc),fnd = 0;\n\t\tfor(int po = 0;po<mod;po+=blc,stinv=mul(stinv,invcc)){\n\t\t\tif(!fnd && ump.count(mul(stinv,z)) && mpow(y,ump[mul(stinv,z)]+po) == z){\n\t\t\t\tcout<<ump[mul(stinv,z)]+po+1<<endl;\n\t\t\t\tfnd = 1;\n\t\t\t}\n\t\t}\n\t\tif(!fnd) cout<<\"-1\\n\";\n\t}\n\treturn 0;\n}\n<\/code><\/pre>\n ","protected":false},"excerpt":{"rendered":"