UVa12893 - Count It(設計解題)

題目大意

請根據題目連結中的程式碼進行優化，讓 \(1 \leq n \leq 10^{18}\) 時也有辦法 AC
題目連結

重點觀念

• 找出此公式的關係式
• 二進位

分析

我們可以發現一些重點

• num[i] = num[i/2] + (i%2)，我們可以發現會延續 num[i/2] +1 or 0。
• 算算看 1 的情況，2 的情況、3 的情況。
• num[1] = 1, num[2] = 2, num[4] = 3，似乎有點二進位的味道？
• 因此也就是將 i 轉換成 2 進位，並且看 2 進位的 i 有幾個 1　？
• 對，就是他了！

心得

腦筋急轉彎…，太狠了。
我怎麼在看解答錢都沒有想出來RRRR，我好笨。拜託，再讓我聰明點八

參考連結

Uva12893 - Count It by txya900619

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
using namespace std;
int t, n;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL

    cin >> t;
    while(t--){
        cin >> n;
        int cnt = 0;
        while(n){ //當 n 為二進位時，有多少個 1
            cnt += n & 1;
            n >>= 1;
        }
        cout << cnt << '\n';
    }
    return 0;
}