解題區/解題區 - UVa

UVa 12431 - Happy 10/9 Day

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

計算 base B 下，每一個 digit 都是 d 的情況，長度為 N，mod M 的結果為何？

Sample Input

1
2
1
3 10 2 10

Sample Output

1
Case 1: 2

Solution

找到

$$d B^{0} + d B^{1} + ... + d B^{N-1} \text{ mod } M \\ \Rightarrow d \frac{B - 1}{B^{N} - 1} \text{ mod } M$$

由於 M 超過 int，運算起來仍有機會 overflow，因此要使用模乘法，也就是相當於直式乘法的運算，防止 (a*b) mod M 溢位。

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
#include <stdio.h> 
long long mul(long long a, long long b, long long mod) { 
    long long ret = 0; 
    for( ; b != 0; b>>=1, (a<<=1)%=mod) 
        if(b&1) (ret += a) %= mod; 
    return ret; 
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = mul(ret, x, mod);
        y >>= 1, x = mul(x, x, mod);
    }
    return ret;
}
long long solve(long long n, long long b, long long d, long long m) {
    // d * (b^n - 1) / (b - 1) mod m
    long long ret;
    ret = mpow(b, n, (b - 1) * m); // b^n mod (b-1) * m
    ret = (ret + (b - 1) * m - 1)/ (b - 1);
    ret = mul(ret, d, m);
    return ret;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n, b, d, m, ret;
        scanf("%lld %lld %lld %lld", &n, &b, &d, &m);
        ret = solve(n, b, d, m);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}