解題區/解題區 - Zerojudge

b432. 趣味加分

contents

  1. 1. Problem
    1. 1.1. 背景
    2. 1.2. 問題描述
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 快速假解
    2. 4.2. 篩選正解

Problem

背景

廖氏如神 (pcsh710742) 在作業中遇到一題，用手算會算到天昏地暗，而問題是這樣子的：

$a^{13337} \equiv n \mod 2^{64}$

其中 $n= 2015 + 2 \times (\text{The last 2 digit of your student ID number})$，請找到 $a < 2^{64}$ 的其中一組解。

問題描述

模數 $2^{64}$ 看起來不大，但對於 Ghz 為 CPU 運算速度單位的電腦而言還是要跑非常久的。因此將問題簡化：

$a^{23333} \equiv n \mod 2^{20}$

現在給予一個 $n$，請求出一組 $a$，測資中保證答案唯一。

Sample Input

1
2
3
4
5
268275
888817
89215
63495
976477

Sample Output

1
2
3
4
5
387
817
639
487
909

Solution

除了偶數無解外，奇數都至少有一個解。而這一題的題目數據恰好奇數都只有一解，那麼就不必處理多組解或者是字典順序最小的，只要專心找到符合的解即可。

  • 暴力建表 $O(2^{20})$ 建完，之後直接查找。
  • 篩選正解，依序窮舉從最低位到最高位 (二進制下) 為 0 還是 1，由於次方會不斷地推移，高位結果不影響低位的對應。窮舉時保留低位符合的解，並且不斷地篩選掉不可能的解方案，複雜度 $O(20 k)$，$k$ 是難以估計的數字。
  • 快速假解，類似篩選正解的做法，但只保留其中一組解進行，複雜度 $O(20)$。這個解法是有點毛病的，但目前找不到反例。

快速假解

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;
long long mul(long long a, long long b, long long mod) { 
    long long ret = 0; 
    for (a %= mod, b %= mod; b != 0; b>>=1, a <<= 1, a = a >= mod ? a - mod : a) { 
        if (b&1) {
            ret += a;
            if (ret >= mod)	ret -= mod;
        } 
    } 
    return ret; 
}
unsigned long long mpow(unsigned long long x, unsigned long long y, unsigned long long mod) {
    unsigned long long ret = 1;
    while (y) {
        if (y&1) 
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret % mod;
}
// find a^23333 = n \mod 2^32
int main() {
    const long long M = 1LL<<20;
    const long long E = 23333;
    long long n;
    while (scanf("%lld", &n) == 1) {
        long long a = 0;
        for (int i = 0; i < 32; i++) {
            long long t = mpow(a, E, M), mask = (1LL<<(i+1))-1;
            if ((t&mask) == (n&mask)) {
                
            } else {
                a |= 1LL<<i;
            }			
        }
        printf("%lld\n", a);
    }
    return 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
#include <bits/stdc++.h> 
using namespace std;
unsigned long long mpow(unsigned long long x, unsigned long long y, unsigned long long mod) {
    unsigned long long ret = 1;
    while (y) {
        if (y&1) 
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret % mod;
}
// find a^23333 = n \mod 2^32
int main() {
    const long long M = 1LL<<20;
    const long long E = 23333;
    long long n;
    while (scanf("%lld", &n) == 1) {
        vector<long long> A(1, 0);
        for (int i = 0; i < 20; i++) {
            vector<long long> nA;
            for (auto &a : A) {
                long long t, mask;
                t = mpow(a, E, M), mask = (1LL<<(i+1))-1;
                if ((t&mask) == (n&mask)) {
                    nA.push_back(a);
                } 
                t = mpow(a|(1LL<<i), E, M), mask = (1LL<<(i+1))-1;
                if ((t&mask) == (n&mask)) {
                    nA.push_back(a|(1LL<<i));
                }			
            }
            A = nA;
        }
        assert(A.size() > 0 && mpow(A[0], E, M) == n);
        printf("%lld\n", A[0]);
    }
    return 0;
}