14283: 【原4283】憨憨求和

题目

题目描述

author: Unknown 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4283

问题描述

铁憨憨表示希望大家机考能AK。

所以铁憨憨觉得应该出简单题。

铁憨憨觉得，要出简单题，那么首先题目的描述必须很简单。

所以这题的题目描述很简单。

铁憨憨希望你能计算出 $$\sum_{a=1}^n\sum_{b=a}^n[\gcd(a, b)=a \oplus b]$$

其中 $\oplus$ 表示异或。$[\ ]$内是一个表达式，当表达式为真它的时值为1，假时为0。

上式的意思就是：在$[1,n]$中有多少对整数$a,b$，满足 $a<b$ 且它们的最大公因数等于它们的异或和。

输入格式

第1行一个整数 $T$，表示数据组数。

对于每一组数据，只有1行1个整数 $n$。

输出格式

对于每一组测试数据，输出1行，表示答案。

样例输入

2
4
233

样例输出

1
327

样例解释

对于 $n=4$ 的情况，只有一对可行的 $a,b$，它是$(2, 3)$. 对于 $n=233$ 的情况，我想到了一个绝妙的解释，可惜这里地方太小写不下。

数据规模

对于所有数据$T\le 5,n\le 2\times 10^7$。

本题由10个测试点组成，通过每一个测试点得到10分。部分测试点的特性如下：

| 测试点 | 特性 | | ------ | ------------------------------------------------ | | 1 | $n\le 100$ | | 2~3 | $n\le 1000$ | | 4~6 | $n\le 10^6$ | | 7 | $n=19260817$ | |8~10| $n\le 2\times 10^7$|

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4283.md
*/
#include <cstdio>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, ans = 0;
int ans2 = 12440306;
void init(){
    n = read();
}
void solve(){
    ans = 0;
    if (n < 10000000){
        ans = (n - 1) >> 1;
        for (int i = 2; i + i <= n; ++i){
            for (int j = i + i; j <= n; j += i) {
                if ((j ^ (j - i)) == i) 
                    ++ans;
            }
        }
    }else {
        ans += ans2 + ((n - 1) >> 1);
        for (int i = 2; i <= 5000000; ++i){
            for (int j = ((10000000 / i) + 1) * i; j <= n; j += i) {
                if ((j ^ (j - i)) == i) 
                    ++ans;
            }
        }
        for (int i = 5000001; i + i <= n; ++i){
            for (int j = i + i; j <= n; j += i) {
                if ((j ^ (j - i)) == i) 
                    ++ans;
            }
        }
    }
    printf("%d\n", ans);
}
int main(){
    int T = read();
    while (T--){
        init();
        solve();
    }
    return 0;
}