题解：P12388 Easy Equation

Noiers · 2025-05-03 00:22:43 · 题解

Easy Equation

解析

因为有 \gcd 在式子中，我们容易想到令：

于是原等式两边同时除以 d 可得：

令 k1\ge k2 可得：

注：d=\gcd(i,j)，k1⊥k2。

我们可以枚举 d,k1,k2，找到满足上式的值，k1>k2 时贡献两次，k1=k2 时贡献一次。把得到的贡献记在 f_{k1\times d} 上，最后前缀和加异或。（不要枚举 i,k1,k2，时间复杂度会多一个 \log，比赛时我就这么超时的。）

优化：

1. 预处理 \operatorname{popcount}(1\sim20000000) 的值。
2. 不难发现 \operatorname{popcount}((k1+k2)\times d) 不大于 \log(2 \times 10^7)，即 k1,k2 不大于 25。

AC 记录。

代码

#include <bits/stdc++.h>
using namespace std;

#define lowbit(x) (x&(~x+1))

const int N=40,mx=25,N2=1e7+10;

int n;
long long ans;
bool st[N][N];//判断互质的数。
long long sum[N2];//贡献和。
int pop[N2<<1];//二进制下数中1的个数。

int gcd(int a,int b){//最大公因数。
    return b==0?a:gcd(b,a%b);
}

void prework(){
  //预处理二进制下数中1的个数。
    for(int i=1;i<=(N2-10)<<1;i++){
        pop[i]=pop[i-lowbit(i)]+1;
    }
  //预处理互质的数。
    for(int i=1;i<=25;i++){
        for(int j=1;j<=i;j++){
            if(gcd(i,j)==1){
                st[i][j]=true;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    prework();
  //枚举d，k1，k2。
    for(int d=1;d<=n;d++){
        for(int i=1;i<=min(25,n/d);i++){
            for(int j=1;j<=i;j++){
                if(pop[i*d+j*d]==i && st[i][j]){
                    if(i!=j)sum[i*d]+=2;
                    else sum[i*d]++;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        sum[i]+=sum[i-1];//前缀和。
        ans^=sum[i];//异或记入答案。
    }
    cout<<ans;
    return 0;
}