首页 > 其他分享 >P4464 [国家集训队] JZPKIL 题解

P4464 [国家集训队] JZPKIL 题解

时间:2022-11-23 19:33:52浏览次数:84  
标签:right frac gcd 题解 sum P4464 nd mu 国家集训队

NOIP 前三天,感觉绝对复习不完了的 gtm1514 认为已经没有什么好害怕的了,于是做起了数学题。

因为摆了大烂所以只有一道。

P4464 [国家集训队] JZPKIL

题意不再赘述。下午看见这题,跟 joke3579 说想稍微休息一下,不整什么花活了,搞点数学。于是就有了这个。

那一点一点拆吧。我不演了我就是想敲点数学式子。

\[\begin{aligned} &\sum_{i=1}^n\gcd(i,n)^x\text{lcm}(i,n)^y\\ =&\sum_{i=1}^n\gcd(i,n)^x\frac{(in)^y}{\gcd(i,n)^y}\\ =&n^y\sum_{i=1}^n\gcd(i,n)^{x-y}i^y\\ =&n^y\sum_{d|n}d^{x-y}\sum_{i=1}^ni^y[\gcd(i,n)=d]\\ =&n^y\sum_{d|n}d^{x-y}\sum_{i=1}^{\frac nd}(id)^y[\gcd(i,\frac nd)=1]\\ =&n^y\sum_{d|n}d^x\sum_{i=1}^{\frac nd}i^y[\gcd(i,\frac nd)=1]\\ =&n^y\sum_{d|n}d^x\sum_{i=1}^{\frac nd}i^y\sum_{e|\gcd(i,\frac nd)}\mu(e)\\ =&n^y\sum_{d|n}d^x\sum_{e|\frac nd}\mu(e)\sum_{i=1}^{\frac nd}(ie)^y\\ =&n^y\sum_{d|n}d^x\sum_{e|\frac nd}\mu(e)e^y\sum_{i=1}^{\frac nd}i^y\\ \end{aligned} \]

等幂求和,拉格朗日插值或者伯努利数。想想发现拉插太麻烦不想搞,于是上伯努利数。简记第 \(i\) 项伯努利数为 \(B_i\)。

\[\begin{aligned} &n^y\sum_{d|n}d^x\sum_{e|\frac nd}\mu(e)e^y\sum_{i=1}^{\frac nd}i^y\\ =&n^y\sum_{d|n}d^x\sum_{e|\frac nd}\mu(e)e^y\sum_{i=0}^y\binom{y+1}iB_i\left(\frac n{ed}\right)^{y+1-i}\\ =&\frac{n^y}{y+1}\sum_{i=0}^y\binom{y+1}iB_i\sum_{d|n}d^x\sum_{e|\frac nd}\mu(e)e^y\left(\frac n{ed}\right)^{y+1-i} \end{aligned} \]

到这我陷入了沉思。所以吃饭之前先把上面的打出来,吃完饭再说下面的。

好了推完了。

前面一堆东西由于 \(y\le 3000\) 可以直接暴力。考虑后面一堆

\[f(n)=\sum_{d|n}d^x\sum_{e|\frac nd}\mu(e)e^y\left(\frac n{ed}\right)^{y+1-i} \]

先看后面。

\[g(n)=\sum_{d|n}\mu(d)d^y\left(\frac nd\right)^{y+1-i} \]

这玩意显然是个积性的。所以 \(f\) 也是积性的。当然筛是不可能筛的,因为 \(n\) 是 \(10^{18}\)。

考虑 \(f(p^k)\) 的取值:

\[f(p^k)=\sum_{a=0}^kp^{xa}\sum_{b=0}^{k-a}\mu(p^b)p^{yb}(p^{k-a-b})^{y+1-i} \]

这个 \(\mu\) 里面一大堆素数幂没啥子用,只需要考虑 \(b=0,1\) 的取值,也就是

\[f(p^k)=\sum_{j=0}^kp^{xj}\left((p^{k-j})^{y+1-i}-p^y(p^{k-j-1})^{y+1-i}\right) \]

然后可以预处理伯努利数,PR 暴力分解 \(n\)。

感觉这一大堆指数看上去就很容易写挂,而且翻了一圈题解发现好像卡常。先去写写,卡不动了再去贺一份实现。

算了懒得写了先把博客发出去,NOIP 以后有空再写。

标签:right,frac,gcd,题解,sum,P4464,nd,mu,国家集训队
From: https://www.cnblogs.com/gtm1514/p/16919554.html

相关文章

  • CF1392H ZS Shuffles Cards 题解
    linkDescription有\(n\)张数字牌以及\(m\)张鬼牌,有一个不可重集合\(S\),初始为空。不断执行以下操作:抽出一张牌,如果为数字牌,则加入\(S\)并移除。如果为鬼牌,如果......
  • Public NOIP Round #3(Div. 1) 题解
    T2:先判\(1,n\)有连边的情况,也就是说明最短路一定是\(1\)直接走到\(n\)。特判掉\(k=1,n=2\)的情况,这是无解的。那么如果\(k\ge2\)就令\(1,n\)都为\(U\),其余随......
  • Codeforces Round #835 (Div. 4) A-G完全题解
    比赛链接A、点击查看代码#include<bits/stdc++.h>usingnamespacestd;intmain(){intT;cin>>T;while(T--){vector<int>G;for(inti=1;......
  • 【MSSQL】SQL SERVER导入中文乱码问题解决
    公司最近承接了一个项目,甲方现使用旧版SiteServer框架(以下简称“SiteCMS”)作为门户网站,使用的数据源是SQLServer。现在需要对SiteCMS进行升级,在升级时数据库和数据库结构也......
  • 题解 LGP7888【「MCOI-06」Distinct Subsequences】
    problem给定一个由小写字符构成的字符串\(S\)。令一个字符串的价值为该串的本质不同非空子序列个数,其中子序列可以为整体。求\(S\)所有子序列的价值和。答案对\(10^......
  • Codeforces Round #790 (Div.4) A-H2题解
    原题链接:https://codeforces.com/contest/1676A.Lucky?题意:给定长度为6由数字组成的字符串问前三个数字的和是否等后三个数字的和。题解:直接相加比较即可。#include<......
  • 题解 LGP2607【[ZJOI2008] 骑士】
    problem基环树森林带权最大独立集。\(n\leq10^6\)。solution0这里先解释一下基环树森林,它就是一个\(n\)个点\(n\)条边的森林,同时是一个荒漠。我们拿出其中一棵连......
  • Codeforces Round #835 (Div.4) A-G题解
    原题链接:https://codeforces.com/contest/1744A.MediumNumber题意:给定三个数,求中间那个数(倒数第二小or倒数第二大)。题解:直接用数组存,sort一下输出中间的数即可。#in......
  • 题解 LGP7489【「Stoi2031」手写的从前】
    problem令\(f_0(S)=\dfrac{\sigma(S)}{\pi(S)}\),\(f_k(S)=\sum\limits_{T\subseteqS}f_{k-1}(T)\)。其中\(\sigma(S)=\sum\limits_{x\inS}x\)为\(S\)中所有元素......
  • 【题解】P2303 [SDOI2012] Longge 的问题
    【题解】P2303[SDOI2012]Longge的问题题目链接求\(\displaystyle\sum_{i=1}^n\gcd(i,n)\)将这个柿子展开变复杂,得到\[\displaystyle\sum_{i=1}^{n}\sum_{d\mid......