Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

LA 6657

Autor(es): Lucas Castro

Considerando, sem perda de generalidade, A > B. Utilizaremos as seguintes propriedades:

GCD(A,B) <= A - B e XOR(A,B) >= A - B

Disso tiramos que GCD(A,B) = A - B. Seja GCD(A,B) = D, nossa dupla será do formato (B + D,B). Onde B é um múltiplo de D.

Logo podemos testar todas as duplas desse formato em O(NlgN)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <iostream>

using namespace std;

#define MAXN 30000010

int pd[MAXN];

int main(){
    int nt;

    for(int i = 1 ; i < MAXN ; i++){
        for(int j = i ; j + i < MAXN ; j+=i){
            if(i == (j^(j + i)))
                pd[j+i]++;
        }
    }
    for(int i = 1 ; i < MAXN ; i++)     pd[i]+=pd[i-1];
    int t = 1;
    scanf(" %d",&nt);
    while(nt--){
        int n;
        scanf(" %d",&n);
        printf("Case %d: %d\n",t++,pd[n]);
    }    
    return 0;
}