A - Odd vs Even

题意

正整数 $N$ が与えられます。$N$ の正の奇数の約数と正の偶数の約数はどちらが多いか答えてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

解析

根据算术基本定理，将 $N$ 分解为

$$N=2^x\prod p_i^{k_i}$$

不难发现，偶因数的个数为 $x\prod(k_i+1)$，奇因数的个数为 $\prod(k_i+1)$。则偶因数的个数比奇因数的个数多当且仅当 $x>1$。

实现

#include <bits/stdc++.h>

int main(){
    int T; std::scanf("%d", &T);
    while(T--){
        long long int x; std::scanf("%lld", &x);
        int cnt = 0;
        while(!(x & 1)) x >>= 1, ++cnt;
        if(!cnt) std::puts("Odd");
        else if(cnt == 1) std::puts("Same");
        else std::puts("Even");
    }
}

来源

AtCoder Regular Contest A - Odd vs Even

评论