核心:奇数的k次方依然是奇数,偶数的k(除零所以要特判)k次方依然是偶数
奇数与偶数的乘机互变性质和01一样,所以奇数视为1,偶数视为0;然后求和并模二(因为奇数加奇数等于偶数)
最后结果如果能整除2便是偶数否则便是奇数
题目描述
给定一个整数 n,它可以被表示为一个 k 位的 b 进制数,如下所示:
n=a1⋅bk−1+a2⋅bk−2+…+ak−1⋅b+ak
举例说明,如果 b=17,k=3,a=[11,15,7],那么 n=11⋅172+15⋅17+7=3179+255+7=3441。
请你判断 n 是奇数还是偶数。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含两个整数 b 和 k。
第二行包含 k 个整数 a1,a2,…,ak。
n 的 b 进制表示不含前导 0,也就是说只有 k=1 时,a1 才有可能是 0。
输出格式
每组数据输出一行结果,n 是偶数则输出 even,奇数则输出 odd。
数据范围
1≤T≤10,
2≤b≤100,
1≤k≤105,
0≤ai<b,
同一测试点内所有 k 的和不超过 105。
样例
输入样例:
4
13 3
3 2 7
10 9
1 2 3 4 5 6 7 8 9
99 5
32 92 85 74 4
2 2
1 0
输出样例:
even
odd
odd
even
算法
(暴力枚举) $O(t*n)$
时间复杂度
枚举每个数字的k位所以应该是10*10^5
结果是10^6左右可以接受
C++ 代码
#include<iostream>
using namespace std;
int main(){
int t;cin>>t;
while(t--){
int b,k;
cin>>b>>k;
int res=0;
int x;
if(b%2==0)x=0;
else x=1;
for(int i=1;i<=k-1;i++){
int y,a;
cin>>a;
if(a%2==0)y=0;
else y=1;
res+=y*x;
}
int a;
cin>>a;
if(a%2==1)res+=1;
if(res%2==1)cout<<"odd"<<endl;
else cout<<"even"<<endl;
}
}