G-Math Test

题意

给定数 、 ，问有多少点对 满足 ，，， 。

思路

参考 zjut_6 队伍代码。

由于 为 ，考虑全部预处理，在每次询问时二分查找答案。

打表可以看出对于满足条件的 ， 也是一组解。所以思路就是每次求出小的解往后迭代。

有 ，即 。故枚举差值 和 ，得到 ，对于每对这样的 求出符合条件的 。

坑点

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

代码

#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();
}