Hackerrank GCD Product(莫比烏斯反演)

来源:https://www.cnblogs.com/zwfymqz/archive/2019/01/04/10221710.html
-Advertisement-
Play Games

題意 "題目鏈接" Sol 一道咕咕咕了好長時間的題 題解可以看 "這裡" cpp include define LL long long using namespace std; const int MAXN = 1e7 + 5e6 + 10, mod = 1e9 + 7, mod2 = 1e9 ...


題意

題目鏈接

Sol

一道咕咕咕了好長時間的題

題解可以看這裡

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 1e7 + 5e6 + 10,  mod = 1e9 + 7, mod2 = 1e9 + 6;
int N, M, vis[MAXN], prime[MAXN], mu[MAXN], f[MAXN], tot;
int add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    return x + y >= mod ? x + y - mod : x + y;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = mul(base, a);
        a = mul(a, a); p >>= 1;
    }
    return base;
}
void sieve(int N) {
    vis[1] = 1; mu[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++tot] = i, mu[i] = -1;
        for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j])) {mu[i * prime[j]] = 0; break;}
            else mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i <= tot; i++) 
        for(LL j = prime[i]; j <= N; j *= prime[i])
            f[j] =prime[i];
    for(int i = 1; i <= N; i++) if(!f[i]) f[i] = 1;
}
signed main() {
    cin >> N >> M;
    sieve(1e7 + 5e6);
    //for(int i = 1; i <= 100; i++) printf("%d %d\n", i, f[i]);
    int ans = 1;
    for(int i = 1; i <= N; i++) {
        if(f[i] == 1) continue;
        ans = mul(ans, fp(f[i], 1ll * (N / i) * (M / i) % mod2));
    }
    cout << ans;
    return 0;
}
/*
100000 50000 200 300
100 2 1 1
*/

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

-Advertisement-
Play Games
更多相關文章
  • Django 系列博客(二) 前言 今天博客的內容為使用 Django 完成第一個 Django 頁面,併進行一些簡單頁面的搭建和轉跳。 命令行搭建 Django 項目 創建純凈虛擬環境 在上一篇博客中已經安裝好了虛擬環境,所以用虛擬環境來安裝指定版本的 Django。為了可以從頭到尾的走一遍流程, ...
  • 計數器 Counter 計數元素迭代器 elements() 計數對象拷貝 copy() 計數對象清空 clear() 有序字典 OrderedDict (對字典的補充,可以記住字典元素添加的順序) 預設字典 defaultdict,(指定字典值的類型) 可命名元組 namedtuple (給元組對 ...
  • 網路編程協議 1.osi七層模型 應用層 表示層 會話層 傳輸層 網路層 數據鏈路層 物理層 2.套接字 socket 有兩類,一種基於文件類型,一種基於網路類型 3.Tcp和udp協議 Tcp協議:面向連接,數據可靠,傳輸效率低,面向位元組流 建立連接與斷開連接的過程(三次握手,四次揮手) 建立連接 ...
  • 1.學習爬蟲,為什麼必須會正則表達式? 我們爬取一些網頁具體內容時,只需要這個網頁某個標簽的一部分內容就足夠,或者是這個標簽的某個屬性的值時,用普通的 xpath 或者css.selector是不能完成的,此時我們就需用到正則表達式去匹配獲取。2.正則表達式官方簡介? 正則表達式,又稱規則表達式。( ...
  • 前言 函數指針是什麼?如何使用函數指針?函數指針到底有什麼大用?本文將一一介紹。 如何理解函數指針 如果有int *類型變數,它存儲的是int類型變數的地址;那麼對於函數指針來說,它存儲的就是函數的地址。函數也是有地址的,函數實際上由載入記憶體的一些指令組成,而指向函數的指針存儲了函數指令的起始地址。 ...
  • 《從零開始PYTHON3》學習資源包下載 課程連載已經完全結束。 經過整理校對,這裡把在課程中出現過的源碼和練習答案示例源碼全部打包提供下載: 提取碼:f3r6 壓縮包解壓密碼:https://formoon.github.io 資源包中還包含了64位Windows版本的Python3安裝包,是驗證 ...
  • 周末小實踐,vue+樹莓派+一言API 一直有個想法,讓樹莓派做後端,實現一個有趣的網路服務。可是,苦於不會前端,遲遲無法動手。最近由於工作任務需要研究了一下前端。 問過前端大佬們,個個都說你得用vue.js,當前最流行、最熱門的前端框架,就用它!聽我的,沒錯! 在大佬的指導下,花了半天時間領略到了 ...
  • 1.簡介 HBase是一個基於HDFS的、分散式的、面向列的非關係型資料庫。 HBase的特點 1.海量數據存儲,HBase表中的數據能夠容納上百億行*上百萬列。 2.面向列的存儲,數據在表中是按照列進行存儲的,能夠動態的增加列並對列進行各種操作。 3.準實時查詢,HBase在海量的數據量下能夠接近 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...