大概刷了 50 題左右 GPE Helper 上面比較常出現的題目，根據題目類型分類做一些筆記，方便之後複習。

本篇主題大多與數學相關。

數學
Problem UVA
22151 Big Mod 374
10559 I Love Big Numbers ! 10220
10422 Is This Integration 10209
10559 10675 Urn-ball Probabilities! 10169
23661 Bit Mask 10718
10414 Bangla Numbers 10101

數學相關

Big Mod

UVA 374

題目大意

根據輸入的數字 B, P, M 求 BPmodMB^P mod M。

解題方法

快速冪的計算方式加上 mod。

注意事項
  • 快速冪函數的參數 b 應該改為 b % m 避免計算時超出 int 範圍。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;

int f(int b, int p, int m){
    if(p == 0) return 1;
    if(p == 1) return b % m;
    int t = f(b, p / 2, m), tt = (t * t) % m;
    if(p % 2 == 0) return tt;
    return (tt * b) % m;
}

int b, p, m;

int main(){
    while(cin >> b >> p >> m){
        cout << f(b % m, p, m) << endl;
    }
    return 0;
}

I Love Big Numbers !

UVA 10220

題目大意

根據輸入的數字 n，求 n! 的各位數字和。

解題方法

因為題目的 n 最大只到 1000，因此可以提前建表，利用一個陣列儲存每一位數字，並利用大數運算的方式逐漸乘上去，每乘一次就紀錄各位數字和。

注意事項
  • 陣列大小要開夠，並且初始值為 1。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> v(1001, vector<int>(3001, 0));
vector<int> ans(1001, 0);

int n;

int main(){
    v[0][0] = 1;
    for(int i = 1; i <= 1000; i++){
        for(int j = 0; j <= 3000; j++){
            v[i][j] = v[i - 1][j] * i;
        }
        for(int j = 0; j < 3000; j++){
            v[i][j + 1] += v[i][j] / 10;
            v[i][j] %= 10;
        }
        for(int j = 0; j <= 3000; j++){
            ans[i] += v[i][j];
        }
    }
    while(cin >> n){
        cout << ans[n] << endl;
    }
    return 0;
}

Is This Integration

UVA 10209

題目大意

根據輸入的數字 a 作為邊長，求正方形分割各區塊的面積。

解題方法
  • z 的面積是正方形減去正三角形以及兩個 1/12 圓， 且網狀線背景區域面積為 4z。
  • y 的面積是正方形減去 1/4 圓以及兩個 z，且點狀背景區域面積為 4y
  • 斜線背景面積為正方形減去 (4y + 4z)。
注意事項
  • pi 的數值多位一點比較精準。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>

using namespace std;

double pi = 3.141592653589793, n;

int main(){
    while(cin >> n){
        double z = n * n * (1 - sqrt(3) / 4 - pi / 6);
        double y = n * n * (1 - pi / 4) - 2 * z;
        printf("%.3f %.3f %.3f\n", n * n - 4 * y - 4 * z, 4 * y, 4 * z);
    }
    return 0;
}

Urn-ball Probabilities!

UVA 10169

題目大意

有兩個罐子，其中一個有一顆紅球，另一個有一顆紅球與白球，每次各從兩個罐子中取出一顆球並放回，並且加入一顆白球，輸入一個數字 n，求出 n 次操作中至少有一次取出兩個紅球的機率，以及連續 n 次都取出兩個紅球的機率小數點後有幾個 0。

解題方法
  • 建立一個陣列 v 儲存 n 次操作中至少有一次取出兩個紅球的機率，可以知道 v[i] = v[i - 1] + (1 - v[i - 1]) / (i * (i + 1))。
  • 建立一個陣列 d 儲存連續 n 次都取出兩個紅球的機率小數點後有幾個 0，因為小數點後 0 的個數應該是 -log(k_n)) 的整數部分 (k_n 為連續 n 次都取出兩個紅球的機率)，k_n = k_(n - 1) * 1 / (i * (i + 1))，把 log 外的負號放進去並且分解，就能得到 d[i] = d[i - 1] + log10(i * (i + 1))。
注意事項
  • 變數 i 用 double 避免精度誤差。
  • 注意題目要求的輸出格式。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>

using namespace std;

vector<double> v(1000001, 0), d(1000001, 0);
int n;

int main(){
    for(double i = 1; i <= 1000000; i++){ //i 用 double
        v[i] = v[i - 1] + (1 - v[i - 1]) / (i * (i + 1));
        d[i] = d[i - 1] + log10(i * (i + 1));
    }
    while(cin >> n){
        printf("%.6f %d\n", v[n], (int)d[n]);
    }
    return 0;
}

Bit Mask

UVA 10718

題目大意

輸入為三個 32 bit 的 unsigned integers N, L, U，求出 M 滿足 L <= M <= U 且使得 N or M 為最大值，如果有多個 M 滿足該條件則傳回最小的。

解題方法

由 32 bit 的最高位開始檢查，如果 N 在此位置為 1 則 M 在此位可以為 0 or 1，為了避免 M < L 超出邊界，必須要檢查 如果 M 在此位以後都為 1 是否能滿足 M >= L。如果 N 在此位置為 0，則要盡可能的使 M 在此位置為 1，因此要檢查 當 M 在此位置為 1 時是否滿足 M <= U。

注意事項
  • (long long)1 << i 前面將 1 轉為 long long 是因為位移之後可能會超過 int 範圍。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;

long long n, l, u;

int main(){
    while(cin >> n >> l >> u){
        long long m = 0;
        for(long long i = 31; i >= 0; i--){ //由最高位往低位檢查
            long long t = ((long long)1 << i), k = (m | t);
            if((n & t)){ // n 此位為 1
                if(m + t - 1 < l) m = k; //是否大於下界
            }else if(k <= u) m = k; // 是否小於上界
        }
        cout << m << endl;
    }
    return 0;
}

Bangla Numbers

UVA 10101

題目大意

將輸入的數字轉換為某種特殊的文字形式。

解題方法

根據四個單位的大小，遞迴處理數字。

注意事項
  • 當數字為 0 時，需要輸出 0。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>

using namespace std;

void solve(long long n){
    if(n / 10000000){
        solve(n / 10000000);
        cout << " kuti";
        n %= 10000000;
    }
    if(n / 100000){
        solve(n / 100000);
        cout << " lakh";
        n %= 100000;
    }
    if(n / 1000){
        solve(n / 1000);
        cout << " hajar";
        n %= 1000;
    }
    if(n / 100){
        solve(n / 100);
        cout << " shata";
        n %= 100;
    }
    if(n){
        cout << " " << n;
    }
}

long long n, c = 0;

int main(){
    while(cin >> n){
        c++;
        printf("%4d.", c);
        if(n) solve(n);
        else cout << " 0";
        cout << endl;
    }
    return 0;
}