BZOJ5118: Fib數列2(二次剩餘)

来源:https://www.cnblogs.com/zwfymqz/archive/2019/03/26/10603943.html
-Advertisement-
Play Games

題意 "題目鏈接" 題目鏈接 一種做法是直接用歐拉降冪算出$2^p \pmod{p 1}$然後矩陣快速冪。 但是今天學習了一下二次剩餘,也可以用通項公式+二次剩餘做。 就是我們猜想$5$在這個模數下有二次剩餘,拉個板子發現真的有。 然求出來直接做就行了 cpp include define Pair ...


題意

題目鏈接

題目鏈接

一種做法是直接用歐拉降冪算出\(2^p \pmod{p - 1}\)然後矩陣快速冪。

但是今天學習了一下二次剩餘,也可以用通項公式+二次剩餘做。

就是我們猜想\(5\)在這個模數下有二次剩餘,拉個板子發現真的有。

然求出來直接做就行了

#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long 
#define LL long long 
#define ull unsigned long long 
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 + 10, mod = 1125899839733759, INF = 1e9 + 10, inv2 = (mod + 1ll) >> 1ll;
const double eps = 1e-9;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}
template <typename A> inline void debug(A a){cout << a << '\n';}
template <typename A> inline LL sqr(A x){return 1ll * x * x;}
template <typename A> A inv(A x) {return fp(x, mod - 2);}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
namespace TwoRemain {
int fmul(int a, int p, int Mod = mod) {
    int base = 0;
    while(p) {
        if(p & 1) base = (base + a) % Mod;
        a = (a + a) % Mod; p >>= 1;
    }
    return base;
}
int fp(int a, int p, int Mod = mod) {
    int base = 1;
    while(p) {
        if(p & 1) base = fmul(base, a, Mod);
        p >>= 1; a = fmul(a, a, Mod);
    }
    return base;
}
int f(int x) {
    return fp(x, (mod - 1) >> 1);
}
struct MyComplex {
    int a, b;
    mutable int cn;
    MyComplex operator * (const MyComplex &rhs)  {
        return {
            add(fmul(a, rhs.a, mod), fmul(cn, fmul(b, rhs.b, mod), mod)),
            add(fmul(a, rhs.b, mod), fmul(b, rhs.a, mod)),
            cn
        };
    }
};
MyComplex fp(MyComplex a, int p) {
    MyComplex base = {1, 0, a.cn};
    while(p) {
        if(p & 1) base = base * a;
        a = a * a; p >>= 1;
    }
    return base;
}
int TwoSqrt(int n) {
    if(f(n) == mod - 1) return -1;
    if(f(n) ==  0) return  0;
    int a = -1, val = -1;
    while(val == -1) {
        a = rand() << 15 | rand();
        val = add(mul(a, a), -n);
        if(f(val) != mod - 1) val = -1;
    }
    return fp({a, 1, val}, (mod + 1) / 2).a;
}
}
using namespace TwoRemain;
signed main() {
    int rm5 = TwoSqrt(5), inv5 = fp(rm5, mod - 2);
    int A = fmul(add(1, rm5), inv2),    
        B = fmul(add(1, -rm5 + mod), inv2);
    int T = read();
    while(T--) {
        int N = read(); int pw2 = fp(2, N, mod - 1);
        int X = fp(A, pw2), Y = fp(B, pw2);
        cout << fmul(X - Y + mod, inv5) << '\n';
    }
    return 0;
}
/*
2
2
124124
*/

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 對於同餘式 $$x^2 \equiv n \pmod p$$ 若對於給定的$n, P$,存在$x$滿足上面的式子,則乘$n$在模$p$意義下是二次剩餘,否則為非二次剩餘 我們需要計算的是在給定範圍內所有滿足條件的$x$,同時為了方便,我們只討論$p$是奇質數的情況 前置定理 $x^2 \equiv ...
  • 近日,微軟在 Github 上開源了一個 Python 靜態類型檢查工具:pyright ,引起了社區內的多方關註。 微軟在開源項目上的參與力度是越來越大了,不說收購 Github 這種大的戰略野心,只說它家開源的 VS Code 編輯器,在猿界已經割粉無數,連我們 Python 圈的紅人 Kenn ...
  • 一、springboot是什麼? 微服務,應該是近年來最火的概念,越來越多的公司開始使用微服務架構,面試中被問到的微服務的概率很高,不管對技術的追求,還是為了進更好的公司,微服務都是我們開發人員的必須要學習的知識。 那麼微服務究竟是什麼呢? 我們通俗的理解方式就是:微服務化的核心就是將傳統的一站式應 ...
  • package main import ( "database/sql" "fmt" "strings" ) import ( _ "github.com/mattn/go-adodb" ) type Mssql struct { *sql.DB dataSource string database ...
  • 列表方法append()和extend()之間的差異: append:在最後追加對象 結果 [1, 2, 3, [4, 5]] extend:通過追加加迭代中的元素來擴展列表。 結果 [1, 2, 3, 4, 5] 作者:阿裡媽媽 鏈接:www.pythonheidong.com/blog/arti ...
  • 1.本地倉庫和apache-mavenbin.zip的下載與解壓 <1.apache-mavenbin.zip下載網址 2.Maven環境變數配置 <1.MAVEN_HOME <2.PATH 3.環境搭建驗證 4自定義數據倉庫的位置(apache-maven.setting.xml)的配置 ...
  • Spring ioc 叫控制反轉,也就是把創建Bean的動作交給Spring去完成。 spring ioc 流程大致為 定位-> 載入->註冊 先說幾個比較有意思的點 1.Spring中的通過IOC生成的Bean是存放在ConcurrentHashMap中的 2.通過xml配置SpringBean時 ...
  • 一、python中如何創建類? 1. 直接定義類 2. 通過type對象創建 在python中一切都是對象 在上面這張圖中,A是我們平常在python中寫的類,它可以創建一個對象a。其實A這個類也是一個對象,它是type類的對象,可以說type類是用來創建類對象的類,我們平常寫的類都是type類創建 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...