UVa 12716 GCD XOR (간단 한 증명)

1149 단어 수학.LCMorGCD
제목: gcd (i, j) = i ^ j 의 대수 (j < = i < = N) N 의 범 위 는 30000000 이 고 10000 조 의 사례 가 있다.
사고방식: GCD (a, b) = a ^ b = c
GCD(a/c,b/c) = 1 (1)
(a-b) <= c (2)
(a/c-b/c) <=1 (3)
(1)(3) => a/c-b/c = 1=> a-b=c 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 30000000+10;
typedef long long LL;
int N;
int ret[maxn];

void init() {
    for(int i = 3; i < maxn; i+=2) ret[i] = 1;
    for(int i = 2; i < maxn/2; i++) {
        for(int j = i+i; j < maxn; j += i) {
            int k = j-i;
            if( (k^j) == i){
                ret[j]++;
            }
        }
    }
    for(int i = 1; i < maxn; i++) ret[i] += ret[i-1];
}
int main(){
    int ncase,T=1;
    init();
    cin >> ncase;
    while(ncase--) {
        scanf("%d",&N);
        printf("Case %d: %d
",T++,ret[N]);
    }
    return 0;
}
각종 모델 매개 변수 집합
Jersey web.xml

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage