---
title: 'UVa 10019 題解 — C++'
disqus: hackmd
---

# UVa 10019 題解 — C++
:::info
:bulb: 此筆記為UVa 10019的題目詳解，包含解題思路、C++範例程式碼。
:::

## Funny Encryption Method (ZeroJudge e545.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=e545)
:::success
一位來自墨西哥蒙特瑞技術研究學院(ITESM Campus Monterrey)的學生想發表一種新的數值加密演算法。
演算法步驟如下：

1. 讀入一個整數N，N為欲加密的數字：N = 265
2. 將N當作十進位的數值：X1 = 265(decimal)
3. 把X1由十進制轉為二進制：X1 = 100001001(binary)
4. 計算二進制的X1有幾個1：b1 = 3
5. 把N當作十六進位數值：X2 = 265(hexadecimal)
6. 把X2由十六進制轉為二進制：X2 = 1001100101(binary)
7. 計算二進制的X2有幾個1：b2 = 5
8. 最後的編碼為N xor (b1*b2)：265 xor (3*5) = 262

這位學生並未通過這次的計算機組識考試，所以他請求校方在ACM的試題上出一題計算共有幾個位元1的題目，好讓他能順利發表他的數值加密演算法。
你必須寫一個程式能讀入一個整數，然後輸出該整數的b1, b2值。
:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
這題將10進制轉換為2進制的方法非常簡單，就是使用「連除法」。當 n > 0 時，將 n 不斷除以 2，所得的餘數就是轉換為 2 進制的結果，同時因為這題要統計 1 出現的次數，因此直接讓 b1 = b1 + j % 2; （加 0 等於沒加）。

這題將16進制轉換為2進制的方法也很粗暴，我直接統計 16 進制的數字 0 ~ 9 轉換為 2 進制時 1 出現的次數，再將 b2 = b2 + hex[x[j]-'0']; 即可統計出 1 出現的次數。

* `0` 對應 `0000`，有 0 個 1
* `1` 對應 `0001`，有 1 個 1
* `2` 對應 `0010`，有 1 個 1
* `3` 對應 `0011`，有 2 個 1
* `4` 對應 `0100`，有 1 個 1
* `5` 對應 `0101`，有 2 個 1
* `6` 對應 `0110`，有 2 個 1
* `7` 對應 `0111`，有 3 個 1
* `8` 對應 `1000`，有 1 個 1
* `9` 對應 `1001`，有 2 個 1
:::

### 範例程式碼

#include <bits/stdc++.h>
using namespace std;

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j, k;
	int t, n;
	
	cin >> t;
	
	for (i=0;i<t;i++) {
		cin >> n;
		
		int b1 = 0, b2 = 0;
		
		for (j=n;j>0;j=j/2)
			b1 = b1 + j % 2;
				
		string x = to_string(n);
		
		int hex[10]={0,1,1,2,1,2,2,3,1,2};
		
		for(j=0;j<x.size();j++)
			b2 = b2 + hex[x[j]-'0'];
		
		cout << b1 << " " << b2 << endl;
	}

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (5ms, 344KB)

###### tags: `CPE 1星`

:::danger
查看更多資訊請至：https://www.tseng-school.com/
:::