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)/ygeq x ，即 x*(y-x)leq a 。故枚举差值 d 和 x ，得到 (x,y) ，对于每对这样的 (x,y) 求出符合条件的 a。
坑点
评测机波动可能会造成样例能过提交后内存超限。
代码
代码语言：javascript复制#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("%dn",(int)(upper_bound(vv[a].begin(),vv[a].end(),n)-vv[a].begin()));
}
int main(){ init();
int _; sc(_); while(_--) solve();
}
