枚举 xor

题意：输入整数n（1<=n<=3千万），有多少对整数（a，b）满足：1<=b<=a<=n，且gcd（a，b）=a XOR b。例如：n=7时，有4对：（3，2），(5,4），(6,4），(7,6）。

思路分析：对于这个问题， gcd(a, b) = c ，则 a ^ c = b , 那么c 一定是 a 的约数，根据这个我们是不就可以去枚举 c 和 a ，类似于素数筛的方法，复杂度是 O(n*logn) 的。对于枚举的 a 和 c 我们都可以计算出来 b ，然后在用 gcd(a, b) 去核验一下，总的复杂度是 n*(logn)^2 ，会 T

这里如果我们对小数据进行打表的话，会发现一个规律，就是 c = a - b，这样的话总的复杂度就会降为 n*logn ，这样提前预处理一遍就可以

至于这个地方要怎么证明，我们显然知道的一个关系式 a - b <= a^b ,a - b >= c ，则由 a-b = c

代码示例：

#define ll long long

const ll maxn = 3e7;

const ll mod = 1e9+7;

const double eps = 1e-9;

const double pi = acos(-1.0);

const ll inf = 0x3f3f3f3f;

ll n;

ll gcd(ll a, ll b){

    return b==0?a:gcd(b,a%b);

}

ll cnt[maxn+5];

void init(){

    for(ll i = 1; i <= maxn/2; i++){ // c

        for(ll j = i*2; j <= maxn; j += i){ // a

            ll b = i^j;

            if (b == 0 || b > j) continue;

            ll fc = abs(j-b);

            //ll fc = gcd(b, j);

            if (i == fc){

                cnt[j]++;

            //    printf("*** %lld %lld %lld\n", j, b, fc);

            }

        }

    }

    for(ll i = 1; i <= maxn; i++) cnt[i] += cnt[i-1];

}

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    ll t;

    ll kase = 1;

    init();

    //for(ll i = 1; i <= 10; i++) printf("%lld ", cnt[i]);

    cin >> t;

    while(t--){

        cin >> n;

        printf("Case %lld: %lld\n",kase++, cnt[n]);

    }

    return 0;

}

巴特西

枚举 xor

最新文章

热门文章