BZOJ_4176_Lucas的数论_杜教筛+莫比乌斯反演
BZOJ_4176_Lucas的数论_杜教筛+莫比乌斯反演
Description
去年的Lucas非常喜欢数论题,但是一年以后的Lucas却不那么喜欢了。
Input
第一行一个整数n。
Output
一行一个整数ans,表示答案模1000000007的值。
Sample Input
Sample Output
HINT
对于100%的数据n <= 10^9。
$f(nm)=\sum\limits_{i|n}\sum\limits_{j|m}[gcd(i,j)=1]$
证明:首先$ij|nm$,但直接枚举$ij$会有些重复。
设$gcd(i,j)=k,a=i/k,b=j/k$
发现一定能枚举到$i'=a*k,j'=b,$和$i''=a,j''=b*k$,此时$gcd(i',j')=gcd(i'',j'')=1$。
考虑$a*b*k$这个约数其实是被枚举了两次,不妨用这两次中的一个来‘代表’$a*b*k*k$。
因此我们枚举$gcd(i,j)=1$的$i,j$即可,只是此时$ij$可能有相等的,他们代表的约数不同。
可以举$n=2,m=6$的例子自己手算一下。
$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}f(ij)
=
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum
\limits_{x|i}\sum\limits_{y|j}[gcd(x,y)=1]$
$=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum
\limits_{x|i}\sum\limits_{y|j}\sum\limits_{d|gcd(x,y)}\mu(d)$
$=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum
\limits_{x|i}\sum\limits_{y|j}\sum\limits_{d|gcd(x,y)}\mu(d)$
$=\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{n/d}\sum
\limits_{x=1}^{\frac{n/d}{i}}\sum\limits_{y=1}^{\frac{n/d}{j}}$
$=\sum\limits_{d=1}^{n}\mu(d)(\sum\limits_{i=1}^{n/d}\frac{n/d}{i})^{2}$
$\mu$的前缀和用杜教筛搞,后面的只有$\sqrt{n/d}$种取值。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
ll mod=1000000007;
map<ll,ll>f;
int m=1000000;
int prime[1000050],cnt,miu[1000050],summiu[1000050];
bool vis[1000050];
ll calc1(ll n) {
if(n<=m) return summiu[n];
if(f.count(n)) return f[n];
ll i,lst,ans=1;
for(i=2;i<=n;i=lst+1) {
lst=n/(n/i);
ans=(ans-(lst-i+1)*calc1(n/i)%mod+mod)%mod;
}
return f[n]=ans;
}
ll calc2(ll n)
{
ll ans=0,i,lst;
for(i=1;i<=n;i=lst+1) {
lst=n/(n/i);
ans=(ans+n/i*(lst-i+1))%mod;
}
return ans*ans%mod;
}
void init() {
int i,j;
miu[1]=summiu[1]=1;
for(i=2;i<=m;i++) {
if(!vis[i]) {
prime[++cnt]=i;
miu[i]=-1;
}
for(j=1;j<=cnt&&i*prime[j]<=m;j++) {
vis[i*prime[j]]=1;
if(i%prime[j]==0) {
miu[i*prime[j]]=0;
break;
}
miu[i*prime[j]]=-miu[i];
}
summiu[i]=summiu[i-1]+miu[i];
}
}
int main() {
init();
ll n,ans=0,i,lst;
scanf("%lld",&n);
for(i=1;i<=n;i=lst+1) {
lst=n/(n/i);
ans=(ans+(calc1(lst)-calc1(i-1)+mod)%mod*calc2(n/i))%mod;
}
printf("%lld\n",ans);
}
最新文章
- 连接到kali linux服务器上的MySQL服务器错误
- Android三种基本的加载网络图片方式(转)
- 【转】很有用但鲜有人知的 Linux 命令
- 在ios中解析json数据
- 关于asp.net 的一些好资料地址 , 防止丢失!
- SignalR 聊天室实例详解(服务器端推送版)
- D3DXCreateTextureFromFileInMemoryEx函数
- oracle查询锁表解锁语句
- maven编译时错误:无效的目标发行版
- Visual Studio图形调试器详细使用教程(基于DirectX11)
- [NOIP提高组2011day1t2]选择客栈
- 使用new Image()进行预加载
- Jmeter在非GUI(命令行)模式下生成测试报告
- 软件工程_10th weeks
- 使用JQuery 合并两个 json 对象
- MAC下Android的Eclipse开发环境的搭建 转自MacroCheng
- Zookeeper架构、ZAB协议、选举
- 全面理解 ASP.NET Core 依赖注入 (转载)
- 【leetcode 简单】第三十八题 两数之和 II - 输入有序数组
- MVC基础知识 – 2.新语法