题解：P12388 Easy Equation

CQ_Bab · 2025-06-05 12:31:08 · 题解

思路

我们考虑化柿子，首先我们可以设 \gcd(x,y)=d 那么我们把 x=d\times a,y=d\times b 然后柿子就变成了 pc(d\times (a+b))\times d=\max(a,b)\times d 然后又变成了 pc(d\times(a+b))=\max(a,b) 那么我们有考虑一下左边这坨柿子的最大值，我们发现最大值能取 22 然后我们枚举的 a,b 都最大是 22 然后我们考虑暴力枚举 a,b 并且要保证 \gcd(a,b)=1 然后我们暴力枚举 d 即可，再看是否合法，如果合法我们发现 \max(a,b)\times d 就为这对值能取到的第一个值，然后我们在用前缀和求出每一个点的准确值即可。

代码

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
//#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
    if(x<0) printf("-"),x=-x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') {ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
}
int T=1;
int n;
const int N=1e7+10;
int a[N],f[N]; 
int cc[N*2];
vector<int>v[30];
int vis[30][30];
void solve() {
    in(n);
    rep(i,1,n*2) cc[i]=cc[i/2]+(i&1);
    rep(a,1,22) {
        rep(b,a,22) {
            if(__gcd(a,b)==1) {
                if(a==b) v[a].pb(b);
                else v[b].pb(a);
            }
        }
    }
    rep(a,1,22) {
        for(auto b:v[a]) {
            int tt=0;
            rep(k,1,n/max(a,b)) {
                if(cc[(a+b)*k]==max(a,b)) {
                    if(a!=b) f[max(a*k,b*k)]+=2;
                    else f[a*k]++;
                }
            }
        }
    }
    int res=0;
    rep(i,1,n) f[i]+=f[i-1],res^=f[i];
    print(res);
}
fire main() {
    while(T--) {
        solve();
    }
    return false;
}

要卡下常。