T8116 密码
题目描述
YJC把核弹发射密码忘掉了……其实是密码被加密了，但是YJC不会解密。密码由n个数字组成，第i个数字被加密成了如下形式：第k小的满足(2^L)|(P-1)且P为质数的P。YJC希望你能帮他算出密码是多少。
输入输出格式
输入格式：
第一行包含一个整数n，表示密码中的数字个数。
接下来n行每行两个整数L和k，表示一个数字的加密形式。
注意，输入格式变更，请注意L和k的先后顺序
输出格式：
输出n行，第i行一个整数，表示第i个数字。
输入输出样例
221 9223 9
1998585857998244353
说明
对于50%的数据，满足18≤n,L≤1000。
对于100%的数据，满足12≤n,L≤500000，保证答案<2^31。
又是一道比赛写挂的题 发现自己比赛码代码很弱啊 这样可不行啊QAQ
————————————————————————————————————
讲一下这道题怎么写吧 首先我们并不需要找出1——2^31-1中的全部素数
因为我们发现我们需要的只是满足k*2^12+1的数就好了 所以我们可以在等差数列上筛质数
先弄出sqrt(末项)以内的质数 （为什么只要到sqrt这个很好证明吧）对每个质数，求出在等差数列上第一个整除位置，以及第二个 然后依次处理
那么要怎么做到在等差数列上筛呢
那么 我们的目标是找出质数p，求哪些a满足(4096a+1)%p==0对吧
4096a+1)%p==0
设4096a+1==kp则(kp-1)%4096==0即kp==1(mod 4096)即k==p^(-1) (mod 4096)于是k是(p模4096的逆元)+4096t，t为整数为了4096a+1最小，直接取逆元有了最小解，又gcd(p,4096)==1——————————————————————
这里证明一下gcd(p,4096)==1
4096x+1=pk
pk-4096x=1当gcd(p,4096)==1时有解——————————————————————————
所以次小解=最小解+4096*p，以此类推然后就能筛完辣剩下的都是满足（p-1）%2^12==0的辣
然后在2^12次方的基础上就能推出剩下的13——31的答案了
然后讲一下一些细节吧
qmod(i,2047,4096)这里是求质数i的逆元 qmod是快速幂 取最小正数解
至于为什么是i^2017%4096是因为
#include#include #include #include #include #define un unsigned intusing namespace std;const int mx=524288;un read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f;}un n,k,l;un cnt[35],num[35][100007];un w[35],f[50007],ed[555555];un qmod(int a,int b,int c){ un ans=1; while(b){ if(b&1) ans=ans*a%c; b>>=1; a=a*a%c; } return ans;}void prepare(){ w[0]=1; for(un i=1;i<=31;i++) w[i]=w[i-1]*2; for(un i=2;i<=50000;i++) if(!f[i]){ for(un j=i*2;j<=50000;j+=i) f[j]=1; if(i==2) continue; if(i%4096==1) num[12][++cnt[12]]=i; for(un x=i*qmod(i,2047,4096)/4096;x