「洛谷P3768」簡單的數學題

来源:https://www.cnblogs.com/ModestStarlight/archive/2018/04/07/8732392.html
-Advertisement-
Play Games

題目鏈接 "簡單的數學題" 題目描述 輸入一個整數n和一個整數p,你需要求出 $$\sum_{i=1}^n\sum_{j=1}^n (i\cdot j\cdot gcd(i,j))\ mod\ p$$ 其中$gcd(a,b)$表示$a$與$b$的最大公約數 輸入 一行兩個整數$p,n$ 輸出 一行一 ...


題目鏈接

簡單的數學題

題目描述

輸入一個整數n和一個整數p,你需要求出
\[\sum_{i=1}^n\sum_{j=1}^n (i\cdot j\cdot gcd(i,j))\ mod\ p\] 
其中\(gcd(a,b)\)表示\(a\)\(b\)的最大公約數

輸入

一行兩個整數\(p,n\)

輸出

一行一個整數,為題目中所求值

樣例

樣例輸入

998244353 2000

樣例輸出

883968974

數據範圍

\(n\leq 10^{10}\)
\(5\times 10^8 \leq p \leq 1.1\times 10^9​\)
\(p​\)為質數(但貌似也可以不是?又不用求逆元)

題解

自己想出來的題!但是連\(WA\)兩發就是因為杜教篩寫掛了……
先不考慮取餘,我們化一下題目中的式子,枚舉\(gcd\)(警告!多公式)。
\[\sum_{i=1}^n\sum_{j=1}^n i\cdot j\cdot gcd(i,j)\] 
\[\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d}\right\rfloor}[i\perp j]i\cdot j \cdot d^2\]
\[\sum_{d=1}^{n}d^3\sum_{i=1}^{\left \lfloor \frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d}\right\rfloor}[i\perp j]i\cdot j\]
\[\sum_{d=1}^{n}d^3\sum_{p=1}^{\left \lfloor \frac{n}{d}\right\rfloor}\mu(p)p^2\cdot \Big(\frac{(1+\left\lfloor \frac{n}{dp}\right\rfloor)\left\lfloor \frac{n}{dp}\right\rfloor}{2}\Big)^2\]

額,現在可以使用分塊優化做到\(O(n)​\)了,但是這完全不能勝任數據範圍,我們換個角度,設\(dp=T​\),枚舉T會有什麼結果?

\[\sum_{T=1}^{n}\Big(\frac{(1+\left\lfloor \frac{n}{T}\right\rfloor)\left\lfloor \frac{n}{T}\right\rfloor}{2}\Big)^2\sum_{d|T}d^3\cdot \mu(\frac{T}{d})(\frac{T}{d})^2\]

\[\sum_{T=1}^{n}\Big(\frac{(1+\left\lfloor \frac{n}{T}\right\rfloor)\left\lfloor \frac{n}{T}\right\rfloor}{2}\Big)^2 T^2\sum_{d|T}d\cdot \mu(\frac{T}{d})\]

現在好像反而變成\(O(n\log n)\)\(O(n\sqrt{n})\)了,別急,我們看看第二層的求和的意義——狄利克雷捲積,這是\(Id\)函數與\(\mu\)函數的狄利克雷捲積,其值就等於\(\varphi\)

\[\sum_{T=1}^{n}\Big(\frac{(1+\left\lfloor \frac{n}{T}\right\rfloor)\left\lfloor \frac{n}{T}\right\rfloor}{2}\Big)^2 T^2\varphi(T)\]

現在,我們只需要快速求出一個東西即可——\(T^2\varphi(T)\),前面的部分可以分塊優化,我們急需解決的就是這個函數\(f(T)=T^2\varphi(T)\)的首碼和\(F(T)\)。顯然,這是一個積性函數。

杜教篩的公式:
\[\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)\cdot g(\frac{i}{d})=\sum_{i=1}^{n}g(i)\sum_{j=1}^{\left\lfloor \frac{n}{i}\right\rfloor}f(j)\]

於是我們需要一個函數與\(f\)捲起來,我們根據套路或枚舉發現\(T^2\)項很惱人,於是嘗試把這一項消掉,於是想到了\(g(x)=x^2\)

\[\sum_{i=1}^{n}\sum_{d|i}d^2\varphi(d)\cdot (\frac{i}{d})^2=\sum_{i=1}^{n}i^2\sum_{j=1}^{\left\lfloor \frac{n}{i}\right\rfloor}f(j)\]
\[\sum_{i=1}^{n}i^2\sum_{d|i}\varphi(d)=\sum_{i=1}^{n}i^2F(\left\lfloor \frac{n}{i}\right\rfloor)​\]

根據公式\(\sum_{d|i}\varphi(d)=i\),繼續變形

\[\sum_{i=1}^{n}i^3=F(n)+\sum_{i=2}^{n}i^2F(\left\lfloor \frac{n}{i}\right\rfloor)\]
\[F(n)=\sum_{i=1}^{n}i^3-\sum_{i=2}^{n}i^2F(\left\lfloor \frac{n}{i}\right\rfloor)\]

由於\(p(i)=i^3\)\(q(i)=i^2\)的首碼和都有公式,我們可以對右邊進行分塊優化,就可以杜教篩了!這道題圓滿解決,時間複雜度\(O(n^{\frac{2}{3}})\)

不過有些小細節要註意,比如模數乘\(2\)可能會爆\(int\)\(n^2\)可能會爆\(long\ long\),需要先取模再平方

\(Code:\)

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 5000005
#define ll long long
map<ll, ll>Phi;
ll n, mod, g[N];
int p[N], h[N], phi[N], cnt;
ll sqr(ll x)
{
    ll a = 2 * x + 1, b = x + 1, c = x;
    if (b % 2 == 0)b /= 2;
    else c /= 2;
    if (a % 3 == 0)a /= 3;
    else
        if (b % 3 == 0)b /= 3;
        else c /= 3;
    a %= mod, b %= mod, c %= mod;
    return a * b % mod * c % mod;
}
ll seq(ll x)
{
    ll a = x + 1, b = x;
    if (a % 2 == 0)a /= 2;
    else b /= 2;
    a %= mod, b %= mod;
    return a * b % mod;
}
ll vas(ll x)
{
    ll a = seq(x);
    return a * a % mod;
}
ll G(ll x)
{
    if (x <= N - 5)
        return g[int(x)];
    if (Phi.find(x) != Phi.end())
        return Phi[x];
    ll ans = vas(x);
    ll lst = 1;
    for (ll i = 2; i <= x; i++)
    {
        i = x / (x / i);
        ll w = (sqr(i) - sqr(lst)) % mod;
        ans = (ans - w * G(x / i) % mod) % mod;
        lst = i;
    }
    if (ans < 0)
        ans += mod;
    Phi.insert(make_pair(x, ans));
    return ans;
}
ll Ans(ll x)
{
    ll ans = 0, lst = 0;
    for (ll i = 1; i <= x; i++)
    {
        i = x / (x / i);
        ll z = seq(x / i);
        z = z * z % mod;
        ans = (ans + z * (G(i) - G(lst)) % mod) % mod;
        lst = i;
    }
    if (ans < 0)
        ans += mod;
    return ans;
}
int main()
{
    phi[1] = 1;
    for (int i = 2; i <= N - 5; i++)
    {
        if (!h[i])
        {
            phi[i] = i - 1;
            p[++cnt] = i;
        }
        for (int j = 1; j <= cnt; j++)
        {
            if (i * p[j] > N - 5)
                break;
            h[i * p[j]] = 1;
            if (i % p[j] == 0)
                phi[i * p[j]] = phi[i] * p[j];
            else
                phi[i * p[j]] = phi[i] * (p[j] - 1);
        }
    }
    cin >> mod >> n;
    for (int i = 1; i <= N - 5; i++)
        g[i] = (g[i - 1] + 1ll * phi[i] * i % mod * i % mod) % mod;
    cout << Ans(n) << '\n';
}

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

-Advertisement-
Play Games
更多相關文章
  • Object構造函數 創建自定義對象最簡單的方式就是創建一個 Object 的實例,然後再為它添加屬性和方法: 缺點 代碼冗餘,會產生大量重覆代碼 無法識別對象(無法知道對象的類型) 對象字面量 對象字面量相比較於 Object 構造函數,代碼會比較直觀一些: 缺點 代碼冗餘,會產生大量重覆代碼 無 ...
  • 原生JavaScript實現頁面回到頂部的功能,如果想實現點擊一個按鈕讓滾動條回到最頂部的功能,首先可能就會想到它是從底部位置移動到頂部的位置 它是一個運動的過程,只要知道當前位置(current Position)和想要到達的位置(target Position)不就可以啦 只不過以前用的都是元素... ...
  • 迭代器在STL運用廣泛,類似容器的迭代已經成為其重要特性,而迭代器模式則是利用迭代器概念進行的抽象運用,迭代器模式運用廣泛和有用,因為其能夠不考慮數據的存儲方式,而是直接面對數據進行迭代,也就是說我們不用考慮集合是數組(或vector)、鏈表、棧還是隊列,而是通過統一的介面進行順序的訪問。 作用 迭 ...
  • 我有點像瘋子,一個人開了一天酒店,來寫這個。我發現我寫這個系列,閱讀的人很少。也許是程式員不重視思想的東西,也許是感覺我寫的很Low,無所謂,我只想告訴同行,程式員重在編程思想,有了編程思想技術的路才能走的更長更遠。我很孤獨,在自己的小世界里存活著。但是我也要耐著孤獨,向更好的方向發展需要孤獨,孤獨 ...
  • 進程的三態模型 細分進程狀態圖 進程的通信 互斥:一次只能供一個進程使用的資源。 同步:多個進程併發進行,可能需要等待。 生產者與消費者 PV操作 PV操作是實現進程同步與互斥的常用方法,在執行期間不可分割。P代表申請一個資源,V代表釋放一個資源。 P操作定義 :S1:=S1-1,若S>=0,則P操... ...
  • 觀察者模式通常的叫法叫做訂閱 發佈模式,類似於報刊雜誌的訂閱,觀察者和被觀察者就是讀者和郵局的關係,讀者先要在郵局訂閱想要的報刊,當報刊發行時,郵局會將報刊郵寄到讀者家裡。觀察者(Observer)和被觀察者(Listener)也是這種關係,Observer將自己attach到Listener中,當 ...
  • 服務拆分具體拆分到多細,業內沒有一個統一的標準。當然也不能為了拆分而拆分,還要依據具體的業務場景應用情況而定,讀過《淘寶技術這十年》的朋友,相信對淘寶的技術演進有一個很直觀的感受。雖然當時微服務的概念並不今天這般火熱,但實際已經在生產環境中運行。 simplemall項目的業務背景基於簡單的購物場景 ...
  • 編譯過程 詞法分析:對源程式從前到後(從左至右)逐個字元地掃描,從而識別出一個個"單詞"符號。 語法分析:判斷語法是否出錯,如表達式、迴圈語句、程式等。 語義分析:檢查如賦值語句左右是否匹配,是否有零除數等。 文法 G={Vt*Vn*S*P} Vt是一個非空有限的符號集合,它的每個元素稱為終結符。 ... ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...