HDUOJ 6555 The Fool

题目链接

Problem Description

The Fool is numbered 0 – the number of unlimited potential –and therefore does not have a specific place in the sequence of the Tarot cards. The Fool can be placed either at the beginning of the Major Arcana or at the end. The Major Arcana is often considered as the Fool’s journey through life and as such, he is ever present and therefore needs no number.

Given n ∈ N+, print the parity of $$\sum _{i=1}^N[\frac{n}{i}]$$，

where [x] = max a (a∈Z,a≤x)

Input

The first line of the input contains one integer T ≤ 100, denoting the number of testcases. Then T testcases follow. In each of the T testcases, there is a positive number n ≤ 1e9.

Output

For each testcase, print a single line starting with “Case i : ”(i indicates the case number) and then “even” or “odd”, separated with a single space.

Sample Input

3 1 10000 100000000

Sample Output

Case 1: odd Case 2: even Case 3: even

找规律题，打表就会发现 $0$ 和 $1$ 以 $3,5,7,9\cdots$ 的等差数列交替出现，然而懒惰的我直接用除法分块算出了答案😀，AC代码如下：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; int n,t; inline ll solve(ll n,ll k) { ll ans=0,j; for (register ll i=1; i <= k; i = j + 1){ j = n / ( n / i ), ans += 1 * (min(j,k) - i + 1) * (n / i); } return ans; } int main(){ scanf("%d",&t); for(int i=1;i<=t;i++){ scanf("%d",&n); int ans=solve(n,n); ans%2?printf("Case %d: odd\n",i):printf("Case %d: even\n",i); } }