當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

关于欧拉工程的一道递推题

發(fā)布時(shí)間：2024/4/11 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了关于欧拉工程的一道递推题小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

今天來講的是在歐拉工程上的一道遞推題，題目描述如下鏈接。

題目：https://projecteuler.net/problem=492

當(dāng)然，這道題在51Nod上有一個(gè)比較通用的版本，鏈接如下

題目：http://www.51nod.com/contest/problem.html#!problemId=1361

題意：給定，并且有，給定兩個(gè)數(shù)和，求的值。其中

???? 滿足和，并且為素?cái)?shù)。

分析：首先對原遞推式進(jìn)行變換得到

???????

?????那么令，繼而有，而。到了這里，假設(shè)

????????

???? 那么我們帶入繼續(xù)遞推會(huì)發(fā)現(xiàn)一個(gè)神奇的結(jié)論

???????

???? 其中假設(shè)取其中一個(gè)解如下

????????

???? 那么得到如下

?????? ?

?????好了，到了這里，最直觀的做法就是根據(jù)上述公式求出，然后會(huì)帶回去求出即可。

???? 如果想用二次剩余的方法來做，因?yàn)榭赡軣o解，所以不能用這種方法做?？闯筛话?/span>

???? 形式的求解，比如下面

?????????

???? 那么回憶之前的一篇文章：http://blog.csdn.net/acdreamers/article/details/8994222，重

???? 點(diǎn)是HDU4565題，這是明顯可以構(gòu)造矩陣的，具體如何構(gòu)造不再贅述。然后先得到遞推式如下

????????

???? 所以最終得到如下

?????????

???? 可以看到矩陣的指數(shù)很大，所以需要降小，而這是一個(gè)經(jīng)典的矩陣找尋環(huán)節(jié)問題。之前有篇文章，如下

???? 鏈接：http://blog.csdn.net/acdreamers/article/details/25616461

???? 當(dāng)時(shí)那道題由于要求最小的循環(huán)節(jié)，所以要求比較精確，必須枚舉因子。但是對于本題不同，我們只要能

???? 求出一個(gè)合理的循環(huán)節(jié)即可，不要求最小的，因?yàn)椴挥绊懽罱K結(jié)果。

???? 參照當(dāng)時(shí)的結(jié)論，由于117不是素?cái)?shù)，所以只有兩種情況。

??????（1）如果117是的二次剩余時(shí)，最小循環(huán)節(jié)是的因子，我們可以取作為循環(huán)節(jié)。

????? （2）如果117是的二次非剩余時(shí)，最小循環(huán)節(jié)是的因子，可以取作

??????????為循環(huán)節(jié)。

???? 到了這里大部分問題都已經(jīng)解決。實(shí)際上當(dāng)117是的二次非剩余時(shí)，循環(huán)節(jié)可以為，至于為什么是

???? 正確的，請來個(gè)大神證明！另外為2或者3時(shí)，需要特判。

代碼：

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h>using namespace std; typedef long long LL;const int N = 2;struct Matrix {LL m[N][N]; };Matrix I = {1, 0,0, 1 };LL quick_mod(LL a, LL b, LL m) {LL ans = 1;a %= m;while(b){if(b & 1){ans = ans * a % m;b--;}b >>= 1;a = a * a % m;}return ans; }LL Legendre(LL a, LL p) { LL t = quick_mod(a, (p - 1) >> 1, p); if(t == 1) return 1; return -1; } Matrix multi(Matrix a, Matrix b, LL m) {Matrix c;for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){c.m[i][j] = 0;for(int k = 0; k < N; k++)c.m[i][j] += a.m[i][k] * b.m[k][j] % m;c.m[i][j] %= m;}}return c; }Matrix power(Matrix A, LL k, LL m) {Matrix ans = I, p = A;while(k){if(k & 1){ans = multi(ans, p, m);k--;}k >>= 1;p = multi(p, p, m);}return ans; }LL GetLoop(LL p) {if(Legendre(117, p) == -1)return p + 1;return p - 1; }int main() {int T;scanf("%d", &T);while(T--){LL n, p;scanf("%lld %lld", &n, &p);if(p == 2 || p == 3){puts("1");continue;}Matrix A;A.m[0][0] = 11 % p;A.m[0][1] = p - 1;A.m[1][0] = 1;A.m[1][1] = 0;LL loop = GetLoop(p);LL x = quick_mod(2, n - 1, loop);x = ((x - 1) % loop + loop) % loop;Matrix ans = power(A, x, p);LL res = (ans.m[1][0] * 119 % p + ans.m[1][1] * 11 % p) % p;res = ((res - 5) % p + p) % p;res = res * quick_mod(6, p - 2, p) % p;printf("%lld\n", res);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的关于欧拉工程的一道递推题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。