QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693173 | #7735. Primitive Root | sjcx | TL | 0ms | 0kb | C++23 | 1.2kb | 2024-10-31 15:39:43 | 2024-10-31 15:40:13 |
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<random>
#include<ctime>
using namespace std;
#define re int
#define ll long long
inline ll read(){
ll x=0,ff=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')ff=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}
return x*ff;
}
inline int hbit(ll x){
for(re i=59;i>=0;i--)
if((x>>i)&1)return i;
return 23333;
}
int main(){
freopen("tt.in","r",stdin);
//freopen("tt.out","w",stdout);
int t=read(),x,y;ll p,m,ss;
while(t--){
p=read();m=read();
if(m==0){
if(p==2)puts("1");
else puts("0");
continue;
}
if(p==2&&m<=3){
if(m<2)puts("1");
else puts("2");
continue;
}
x=hbit(p-1);y=hbit(m);
if(x>=y){
if(m>=p)puts("1");
else puts("0");
continue;
}
ll u=m&(((1ll<<(y+1))-1)^((1ll<<(x+1))-1));
ll v=m-u;
ss=(u-1)/p+(((u-1)%p)>=1);
ll _u=u;u%=p;u^=((p+1-u)%p)^(p-1);
if(u<=v)ss++;
_u%=p;
if(_u+p<(1ll<<(x+1))){
_u^=((p+1-_u)%p+p)^(p-1);
if(_u<=v)ss++;
}
printf("%lld\n",ss);
}
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3 2 0 7 11 1145141 998244353