2020牛客暑期多校训练营(第十场)

8.10 只想着G赛后也过了G的牛客10

A-Permutation

题意

给定一个质数 $p$ ,求出 $p-1$ 个数组成的序列,要求序列满足 $x_{i+1}=2x_i$ 或 $x_{i+1}=3x_i$

思路

如果序列有解,则 $x_1=1,x_2=2$ 然后依序构造,判断 $x_{i-1}*2%p$ 和 $x_{i-1}*3%p$ 是否有满足条件的解。

G-Math Test

题意

给定数 $a$ 、$n$ ,问有多少点对 $(x,y)$ 满足 $gcd(x,y)=1$,$y∣(x^2+a)$,$x∣(y^2+a)$,$1≤x≤y≤n$ 。

思路

参考 ==zjut_6== 队伍代码。

由于 $T$ 为 $1e6$ ,考虑全部预处理,在每次询问时二分查找答案。

打表可以看出对于满足条件的 $(x,y)$ ,$(y,(y^2+a)/x)$ 也是一组解。所以思路就是每次求出小的解往后迭代。

有 $(x^2+a)/y\geq x$ ,即 $x*(y-x)\leq a$ 。故枚举差值 $d$ 和 $x$ ,得到 $(x,y)$ ,对于每对这样的 $(x,y)$ 求出符合条件的 $a$。

坑点

评测机波动可能会造成样例能过提交后内存超限。

代码

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
58
59
60
61
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 1e5 + 1;
vector<ll>vv[maxn+5];
vector<pii>rt[maxn+5];
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=1; y=0; return; }
exgcd(b,a%b,y,x); y-=(a/b)*x; return;
}
ll inv(ll a,ll p){
ll x,y; exgcd(a,p,x,y);
return (x%p+p)%p;
}
void init(){
rep(a,1,maxn) rt[a].push_back(pii(1,1));
// 对于任意a都有1,1满足条件
rep(d,1,maxn) for(int x=1;1ll*x*d<maxn;++x){
// 枚举y和x的差值d和x
if(__gcd(d,x)>1) continue;
// 差值和x不互质则x和y也不互质
int y=x+d; ll m=1ll*x*y;
ll k1=inv(y,x),k2=inv(x,y);
ll t1=-1ll*y*y%x,t2=-1ll*x*x%y;
while(t1<0) t1+=x;
while(t2<0) t2+=y;
ll a=k1*y%m*t1%m;
a+=k2*x%m*t2%m; a%=m;
// crt
while(a<1ll*x*d) a+=m;
while(a<maxn){
rt[a].emplace_back(pii(x,y));
a+=m; // 加xy不影响取模的结果 前后a是等价的
}
}
rep(a,1,maxn){
rep(i,0,(int)rt[a].size()){
ll x=rt[a][i].first,y=rt[a][i].second;
__int128 t=(__int128)y*y+a; t/=x;
if(t>1e18) continue; x=y; y=t;
rt[a].push_back(pii(x,y));
// 更新 这个打表一下就找到规律了
} sort(rt[a].begin(),rt[a].end());
int sz=unique(rt[a].begin(),rt[a].end())-rt[a].begin();
rep(i,0,sz) vv[a].push_back(rt[a][i].second);
sort(vv[a].begin(),vv[a].end());
rt[a].resize(0); rt[a].shrink_to_fit();
}
}
int solve(){
int a; ll n; sc(a); scl(n);
return pf("%d\n",(int)(upper_bound(vv[a].begin(),vv[a].end(),n)-vv[a].begin()));
}
int main(){ init();
int _; sc(_); while(_--) solve();
}