题面

有

T 组数据，每次给出一个数

N ，问

N 的所有因数(包括

1 和

N)中奇因数个数和偶因数个数的关系（“>”，“<”，还是“=”）。

≤

N\leq 1e18,T\leq 2e5

N≤1e18,T≤2e5.

题解

如果把一个数进行质因数分解，那么我们枚举每一个质因数的出现次数(幂的大小)就可以得到所有因数。

所以固定同一个质因数的出现次数后，对应的因数个数相等（都是其它质因数最高幂次+1的乘积）。

我们还知道一个正整数为偶数当且仅当质因数分解后有 2，一个正整数为奇数当且仅当质因数分解后没有 2 。

那么就可以推出一个结论了：如果

N 的质因数分解中 2 的幂次（这个可以用

N 不断除以 2 得到）大于等于 2，说明偶因数个数至少是奇因数的两倍，偶因数大于奇因数；如果等于 1，说明偶因数个数等于奇因数；否则等于 0，说明所有因数都是奇数。

由于只需要得到 2 的幂次与 1 的关系，不太需要直到它具体有多大，所以时间复杂度

(

)

O(T)

O(T).

CODE

#include<cstdio>

#define LL long long

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f * x;

}

int main() {

	int T = read();

	while(T --) {

		LL N = read();

		int ct = 0;

		while(!(N&1) && ct < 2) N >>= 1,ct ++;

		if(ct == 0) printf("Odd\n");

		else if(ct == 1) printf("Same\n");

		else printf("Even\n");

	}

	return 0;

}

巴特西

ARC116 A Odd vs Even （质因数分解，结论）

题面

题解

CODE

最新文章

热门文章