C題：

C題題目鏈接

題目描述：

T^T又有數學問題了

T^T 是個很厲害的選手,除了喜歡寫17kb+的代碼題,偶爾還會寫數學題.他找到了一個數列:

他給了你幾個數:n,a,b,c,你需要告訴他fn模p後的數值.

第一行一個數T,為測試數據組數.

每組數據一行,一行五個正整數,按順序為n,a,b,c,p.

1≤T≤10,1≤n≤10^18,1≤a,b,c≤10^9,p是質數且p≤10^9+7

對每組數據輸出一行一個數,輸出fn對p取模後的數值.

1
5 3 3 3 233

190

這道題沒有完整代碼提供，因為這道題還有沒有弄明白的地方，而且雛形代碼一直沒調試好:-(，這裡提供簡要思路

對於這樣的題目，一開始拿到手的時候沒有什麼明朗的思路，因此我們可以試著枚舉前幾項，看看是否從特殊的角度發現其一般規

律。

f1 = 1;

f2 = a^b;

f3 = a^b * a^(bc) * 1 = a^[b(1+c)];

f4 = a^b * f3^c * f2 = a^[b(c^2 + c + 2)];

f5 = a^b * f4^c * f3 = a^[b(c^3 + c^2 + 3*c + 2)];

f6 = a^b * f5^c * f4 = a^[b(c^4 + c^3 + 4 * c ^ 2 + 3*c + 3)];

枚舉到第六項，我們發現，每一項都有其相同的部分，因此我們可以去掉相同的部分，看剩余不同的部分是否有規律：

0 ---------> f1

1 ---------> f2

1+c ---------> f3

c^2 + c + 2 ---------> f4

c^3 + c^2 + 3*c + 2 ---------> f5

c^4 + c^3 + 4 * c ^ 2 + 3*c + 3 ---------> f6

仔細觀察，其實不難發現，每一項(第三項及第三項之後)都與其前兩項是有聯系的。比如說f3，f4，f5.我們可以找到它們之間的這樣

的關系：

f3 + f4 * c + 1 = f5；

而有了這樣的推論之後，我們可以發現：f(n) = c * f(n-1) + f(n-2) + 1;

而多項式之間的關系，則可以借助於矩陣來解決，對於有常數項的多項式，則用三維矩陣即可(常數視為第三維)。

因此有了以上的推論，我們可以構造出這樣的初始矩陣以及冪矩陣：

因此我們則可以將初始矩陣記為A矩陣，冪矩陣記為B矩陣，這樣的話，要求fn，則即求A * B ^ (n-1),然後取結果矩陣的首項即可。

而要求A * B ^ (n-1)，則可用矩陣快速冪求解。

但是，這道題還有兩個要注意的小細節：

1.B ^ (n-1)指數過大，long long已經無法存儲，我個人有個想法：

(1).對等式兩邊運用log函數，以a為底，這樣的話，就把冪指數降下來了。

(2).第二個辦法是從福州大學陳鴻數論pdf文檔中看到了一個結論：

這個結論我暫時沒有辦法解釋，涉及到歐拉函數和費馬小定理，證明過程在這裡，有興趣的可以一起研究探討：

求解x=a^b(mod m)

2.注意特判a與p不互質(a mod p = 0)的情況。

E題：

E題題目鏈接

題目描述：

Complicated GCD

Greatest common divisorGCD(a,?b)of two positive integersaandbis equal to the biggest integerdsuch that both integersaandbare divisible byd. There are many efficient algorithms to find greatest common divisorGCD(a,?b), for example, Euclid algorithm.

Formally, find the biggest integerd, such that all integersa,?a?+?1,?a?+?2,?...,?bare divisible byd. To make the problem even more complicated we allowaandbto be up to googol,10100— such number do not fit even in 64-bit integer type!

The only line of the input contains two integersaandb(1?≤?a?≤?b?≤?10100).

Output one integer— greatest common divisor of all integers fromatobinclusive.

1 2

1

61803398874989484820458683436563811772030917980576 61803398874989484820458683436563811772030917980576

61803398874989484820458683436563811772030917980576

給定a,b,找出能夠整除閉區間[a,b]中所有的數的最大整數。

解析：

簡單題，考慮當a == b時，顯然這個數就是其本身，而當a != b時，由於連續的兩個正整數的公共因子只有1(可用反證法證明)，因此

答案則是1.

完整代碼實現：

#include
#include
using namespace std;
int main(){
    string a,b;
    cin >> a >> b;
    if(a==b){
        cout << a << endl;
    }
    else{
        cout << 1 << endl;
    }
    return 0;
}

F題題目鏈接

題目描述：

Solve equation

You are given two positive integers A and B in Base C. For the equation:

We know there always existing many non-negative pairs (k, d) that satisfy the equation above. Now in this problem, we want to maximize k.

For example, A="123" and B="100", C=10. So both A and B are in Base 10. Then we have:

(1) A=0*B+123

(2) A=1*B+23

As we want to maximize k, we finally get one solution: (1, 23)

The range of C is between 2 and 16, and we use 'a', 'b', 'c', 'd', 'e', 'f' to represent 10, 11, 12, 13, 14, 15, respectively.

The first line of the input contains an integer T (T≤10), indicating the number of test cases.

Then T cases, for any case, only 3 positive integers A, B and C (2≤C≤16) in a single line. You can assume that in Base 10, both A and B is less than 2^31.

3
2bc 33f 16
123 100 10
1 1 2

(0,700)
(1,23)
(1,0)

給定一個數T，表示有T組測試數據，然後每行有三個數，分別是A,B,C。C表示給定的A,B數的進制，然後題目要求你將A,B轉換成十

進制後，找出一個最大的數k，使得k，d滿足A = k * B + d(其中k，d均為非負整數)。

解析：

顯然我們要將其轉換成十進制數之後，然後按照格式輸出即可。注意這道題不要去用pow()函數從後往前計算A,B兩數十進制所表示

的數，會判CE或者WA，原因未知。無論如何，涉及到浮點數的函數，還是要慎用，能不用則不用。

因此我們從前往後考慮即可，每往後計算一位，則標記數乘以相應進制即可。

完整代碼實現：

#include
#include
#include
using namespace std;
typedef long long ll;
void solve(){
    int T,radix,tmp;
    char str1[50],str2[50];
    scanf("%d",&T);
    while(T--){
        scanf("%s %s %d",str1,str2,&radix);
        int a = 0,b = 0;
        for(int i = 0;str1[i] != '\0';++i){
            a *= radix;
            if(str1[i] >= 'a'){
                a += str1[i] - 'a' + 10;
            }
            else{
                a += str1[i] - '0';
            }
        }
        for(int i = 0;str2[i] != '\0';++i){
            b *= radix;
            if(str2[i] >= 'a'){
                b += str2[i] - 'a' + 10;
            }
            else{
                b += str2[i] - '0';
            }
        }
        //printf("%d %d",a,b);
        printf("(%d,%d)\n",a/b,a%b);
    }
}
int main(){
    solve();
    return 0;
}