【JZOJ4919】【NOIP2017提高组模拟12.10】神炎皇
题目描述
神炎皇乌利亚很喜欢数对,他想找到神奇的数对。
对于一个整数对(a,b),若满足a+b<=n且a+b是ab的因子,则成为神奇的数对。请问这样的数对共有多少呢?
数据范围
对于100%的数据n<=100000000000000。
=w=
引理一
两个互质的数之差与这两个数互质。
证明:
证明依赖于欧几里得算法的gcd(a,b)=gcd(b,a−b)。
1.设a>b,r=(a,b),则有r|a,r|b,表示成a=a′∗r,b=b′∗r。
则有(b,a−b)=(b′∗r,(a′−b′)∗r),显然(b,a−b)也有r这个公约数。
2.设r=(a,b),则有r|a,r|b,表示成a=a′∗r,b=b′∗r。
则有(a+b,a)=((a′+b′)∗r,a′∗r),显然(a+b,a)也有r这个公约数。
综合1,2,(a,b)的公约数也是(b,a−b)的公约数,所以gcd(a,b)=gcd(b,a−b)。
回到原命题,gcd(p,q)=1⇒gcd(q,p−q)=1。
引理二
两个互质的数的和与积互质。
证明:
设gcd(p,q)=1,
根据引理一,则有
gcd(p+q,q)=gcd(q,p)=1,gcd(p+q,p)=gcd(p,q)=1
也就是说(p+q)与p和q都互质,必然就和pq互质。
正文
若(a,b)合法,那么存在(a+b)|ab
设d=gcd(a,b),并且a′∗d=a,b′∗d=b。
那么就有(a′+b′)d|a′b′d2,即(a′+b′)|a′b′d。
根据引理二,又a′与b′互质,则(a′+b′)|d。
题设有a+b<=n,那么(a′+b′)d<=n。
由(a′+b′)|d,d至少为(a′+b′)。
又(a′+b′)d<=n,那么(a′+b′)<=n√。
不妨枚举i=(a′+b′),这样d就只能取n/i个了,每隔i个有一个d|i。
所以合法的d就有n/i2个。
再来考虑符合(a′+b′)=i的个数,由引理一:
如果存在一个gcd(c,i)=1,那么必然存在一个gcd(c,i−c)=1。
于是乎,(a′+b′)=i的个数即为φ(i),可用线性筛法预处理。
综上,ans=∑n√i=2ni2∗φ(i)。
时间复杂度为O(n√)。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
const char* fin="uria.in";
const char* fout="uria.out";
const int inf=0x7fffffff;
const int maxn=10000007;
ll n,i,j,k,nq;
ll ans;
ll p[maxn],phi[maxn];
bool bz[maxn];
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%lld",&n);
nq=(ll)sqrt(n);
for (i=2;i<=nq;i++){
if (bz[i]==false){
phi[i]=i-1;
p[++p[0]]=i;
ans+=phi[i]*(n/i/i);
}
for (j=1;j<=p[0];j++){
k=i*p[j];
if (k>nq) break ;
if (i%p[j]==0) phi[k]=phi[i]*p[j];
else phi[k]=phi[i]*(p[j]-1);
bz[k]=true;
ans+=phi[k]*(n/k/k);
if (i%p[j]==0) break;
}
}
printf("%lld\n",ans);
return 0;
}
=o=
线性筛法求欧拉函数
首先有通式,
φ(p1k1∗p2k2∗...∗pnkn)=(p1−1)∗p1k1−1∗(p2−1)∗p2k2−1∗...∗(pn−1)∗pnkn−1。
显然用线筛通过简单转移可以得到。
~
一开始我也考虑分析这个东西,
(a,b)合法就有(a′+b′)|a′b′d。
然后就不会了。
并没有考虑到gcd(a′+b′,a′b′)=1这个性质。
日后这种数论计数问题,先从合法的开始分析。
如果涉及倍数关系,可以考虑排除一些不作贡献的干扰项。
最新文章
- vs快捷方式
- maven 工程启动找不到 Spring ContextLoaderListener 的解决办法
- log4j使用教程详解(怎么使用log4j2)
- Puppet master/agent installation on RHEL7
- docker配置环境
- 使用更清晰DebugLog开发和调试工具
- MySQL主从同步和读写分离的配置
- centos7.2构建Python3.5开发环境
- JDK源码分析(11)之 BlockingQueue 相关
- react用class关键字来创建组件
- JavaScript踩坑
- 【python】——sql模拟
- python学习Day3 变量、格式化输出、注释、基本数据类型、运算符
- python 多线程操作数据库
- mysql代理之Atlas
- 【easyswoole】 解决安装报错
- elasticsearch 6.0java api的使用
- Hive安装与应用过程
- (一)C的编译,printf,规范化
- Python常用库之一:Numpy
热门文章
- CentOS7.4 安装JDK 步骤
- Spinrg WebFlux中Cookie的读写
- hibernate 注释多表 级联操作
- LA3882 And Then There Was One
- Codeforces 142D(博弈)
- NoClassDefFoundError: Could not initialize class org.apache.cxf.jaxrs.provider.ProviderFactory org.springframework.aop.support.AopUtils.isCglibProxyClass
- global.fun.php
- Highcharts 饼图数值显示在图形上
- JQuery或JS判断浏览器内核版本号以及是否支持W3C盒子模型
- Java review-basic2