bzoj3944 Sum

来源:https://www.cnblogs.com/wxyww/archive/2019/12/25/bzoj3944.html
-Advertisement-
Play Games

"題目鏈接" problem 給出一個$n,n include include include include include include include include using namespace std; typedef long long ll; const int N = 50001 ...


題目鏈接

problem

給出一個\(n,n < 2^{31}\)。分別求

\[\sum\limits_{i=1}^n\varphi(i),\sum\limits_{i=1}^n\mu(i)\]

solution

\(\varphi(i)\)\(\mu(i)\)都是積性函數。

\(\varphi(p^k)=(p-1)p^{k-1}\),所以可以直接\(Min\_25\)篩了。

因為\(\varphi(p)=p-1,p是質數\),g函數不好處理

所以將\(\varphi(p)\)分為兩個函數\(f_1(p)=p,f_2(p)=1\)。然後分別求\(g\)\(h\)

\(\mu\)預處理就直接是\(-h\)了。

然後\(Min\_25\)篩模板就行了。

RP--

跑了9964ms

code

/*
* @Author: wxyww
* @Date:   2019-12-25 20:16:31
* @Last Modified time: 2019-12-25 21:38:39
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 500010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    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;
}
ll m,n,pri[N],vis[N],js,tot,g[N],h[N],sum[N];
void pre() {
    for(int i = 2;i <= 500000;++i) {
        if(!vis[i]) pri[++js] = i,sum[js] = sum[js - 1] + i;
        for(int j = 1;j <= js && 1ll * pri[j] * i <= 500000;++j) {
            vis[pri[j] * i] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}
ll w[N],id1[N],id2[N];
ll Sphi(ll now,ll x) {
    if(now <= 1 || pri[x] > now) return 0;
    
    ll k;

    if(now <= m) k = id1[now];
    else k = id2[n / now];
    ll ret = g[k] - h[k] - sum[x - 1] + x - 1;

    for(int k = x;k <= tot && pri[k] * pri[k] <= now;++k) {
        ll p = pri[k];
        for(int e = 1;p * pri[k] <= now;++e,p *= pri[k]) {
            ret += (pri[k] - 1) * (p / pri[k]) * Sphi(now / p,k + 1) + p * (pri[k] - 1);
        }
    }
    return ret;
}
ll Smu(ll now,ll x) {
    if(now <= 1 || pri[x] > now) return 0;

    ll  k;
    if(now <= m) k = id1[now];
    else k = id2[n / now];

    ll ret = -h[k] + x - 1;
    for(int k = x;k <= tot && pri[k] * pri[k] <= now;++k) {

            ret -= Smu(now / pri[k],k + 1);
    } 
    return ret;
}
void solve() {
    m = sqrt(n);
    if(!n) return (void)puts("0 0");
    tot = 0;
    // memset(g,0,sizeof(g));memset(h,0,sizeof(h));

    for(ll l = 1,r;l <= n;l = r + 1) {
        r = n / (n / l);
        w[++tot] = n / l;
        if(n / l <= m) id1[n / l] = tot;
        else id2[r] = tot;

        g[tot] = ((w[tot] + 2) * (w[tot] - 1)) / 2;
        h[tot] = w[tot] - 1;

    }
    // puts("!!");
    for(int j = 1;j <= js && pri[j] <= m;++j) {
        for(int i = 1;i <= tot && 1ll * pri[j] * pri[j] <= w[i];++i) {
            ll tmp = w[i] / pri[j];
            int k;
            if(tmp <= m) k = id1[tmp];
            else k = id2[n / tmp];

            g[i] -= pri[j] * (g[k] - sum[j - 1]);
            h[i] -= h[k] - j + 1;
        }
    }

    // for(int i = 1;i <= tot;++i) printf("%lld ",h[i]);
    // puts("");
    // puts("!");
    cout<<Sphi(n,1) + 1 <<" "<<Smu(n,1) + 1<<endl;
    // puts("!!!");
}
int main() {
    int T = read();
    
    pre();

    while(T--) {
        n = read();solve();
    }

    return 0;
}

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

-Advertisement-
Play Games
更多相關文章
  • 這份資源是我經過多年積累才整理歸類出來,有很多電子書我覺質量還是非常高的,由於電子書太多我也是用業餘時間挑著看的,這麼多資源自己保存著也是浪費,就想著現在把資源分享出來,希望能真正幫到大家; 資源我都整理在網盤了,之前分享出來的鏈接沒過幾天就自動取消,我就在文章底部放了二維碼,需要的添加好友就行了, ...
  • 一、僅做瞭解 //用戶組的處理 public class TestUserGroup { private ProcessEngine processEngine=ProcessEngines.getDefaultProcessEngine(); //創建用戶和用戶組 @Test public voi ...
  • 流程中的某個任務由指定的group來完成,其中group由多個user組成。 一、直接指定辦理組 1、流程圖 2、部署和啟動流程 //部署流程 @Test public void bushu() { InputStream inputStream = this.getClass().getResou ...
  • 一、流程圖 二、分配個人任務的方式 1、直接指定辦理人 說明:這樣分配辦理人不夠靈活,因為項目開發中任務的辦理人不要放置在XML當中實際開發中辦理人是不固定的。 2、使用流程變數指定辦理人 2.1 流程圖中的設置 說明:在Activiti中#{username}和${username}的意義是一樣的 ...
  • 一、接收任務 接收任務(ReceiveTask)即等待任務,接收任務是一個簡單任務,它會等待對應消息的到達。當前,官方只實現了這個任務的java語義。 當流程達到接收任務,流程狀態會保存到資料庫中。在任務創建後,意味著流程會進入等待狀態,直到引擎接收了一個特定的消息, 這會觸發流程穿過接收任務繼續執 ...
  • Java JDBC 資料庫鏈接小結隨筆 一、鏈接資料庫的步驟 二、 關於Statement 和 PrepareStatement 兩者區別 用法 三、關於 ResultSet 的一些小結 四、自定義工具類的封裝 五、一些異常的解釋 一、鏈接資料庫的步驟 註冊驅動 獲得鏈接對象 創建sql容器 執行s ...
  • 簡介 Min_25篩~~據說~~可以在$O(\frac{n^{\frac{3}{4}}}{logn})$處理出含有以下性質的函數f的首碼和: 1.$f(ab)=f(a)f(b)$,即f是一個積性函數 2.$f(p^k)$可以快速計算。 PS:本文沒有關於複雜度的證明。。。 預處理 首先要預處理兩個東 ...
  • springboot集成開發實現商場秒殺 加入主要依賴 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-thymeleaf</artifactId> </dependen ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...