Codeforces Global Round 1 A. Parity(数学思维)

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

24

You are given an integer n (n≥0) represented with k digits in base (radix) b. So,

n=a1⋅bk−1+a2⋅bk−2+…ak−1⋅b+ak.
For example, if b=17,k=3 and a=[11,15,7] then n=11⋅172+15⋅17+7=3179+255+7=3441.

Determine whether n is even or odd.

Input
The first line contains two integers b and k (2≤b≤100, 1≤k≤105) — the base of the number and the number of digits.

The second line contains k integers a1,a2,…,ak (0≤ai

The representation of n contains no unnecessary leading zero. That is, a1 can be equal to 0 only if k=1.

Output
Print “even” if n is even, otherwise print “odd”.

You can print each letter in any case (upper or lower).

Examples
input
13 3
3 2 7
output
even
input
10 9
1 2 3 4 5 6 7 8 9
output
odd
input
99 5
32 92 85 74 4
output
odd
input
2 2
1 0
output
even

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;#define PI acos(-1.0)
typedef long long ll;
typedef pair pii;
typedef pair pll;	
const int INF32M=0x3f3f3f3f;
const ll INF64M=0x3f3f3f3f3f3f3f3f;
const int maxn=1e5+5;
int a[100005];	//k个系数 
int main()
{ios::sync_with_stdio(false);int b,k,cnt=0;cin>>b>>k;for(int i=1;i<=k;i++)cin>>a[i];if(b%2==0){if(a[k]%2==0)	//ak为偶数 cout<<"even"<

观察多项式
b为偶数 b^k为偶数 系数无论奇数偶数
奇乘偶=偶 偶乘偶=偶
只需要考虑ak奇偶性 偶+奇=奇 偶+偶=偶
b为奇数 b^k为奇数 偶系数不管 得偶
cnt判断奇系数有几个 b^k乘奇系数=奇
奇+奇=偶 偶+奇=奇
奇系数有几个意味着奇数项有几个
奇数项有偶数个 加法为偶数
奇数项有奇数个 加法为奇数 偶(偶系数*b^k=偶)+奇=奇