看到这是一道紫题还是和gcd有关的才点进来(毕竟数论只会gcd).
前置芝士
- 质数**(又称素数):因数只有1和本身,但是很特殊的1不是一个质数.
- gcd**:欧几里得算法,又称辗转相除法,可以在约为O(LogN)的时间复杂度内求出两个数的最大公约数(N为两个数中大的那个数,在两数为相邻的斐波那契数时最慢,具体不证明
其实就是我不会). - 欧拉函数**:一个非常基本的数论函数,是一个积性函数(
虽然本题并没有考到),欧拉函数可以表示为(varphi(x)),表示小于x的自然数中与x互质的数的个数(具体求法下文会讲到).
推导公式
很明显,直接暴力需要O(N^2)的时间发咋读但是N有1e7肯定是会T的,所以需要从gcd(a,b)为一个质数入手.
当(gcd(a,b)==1)时不难发现(gcd(a*p,b*p)==p)(p为任何自然数时都成立),于是乎可以先把0~N中的素数筛出来.
那么下面要怎么知道一个素数可以产生几对符合条件的a,b呢?
可以发现(max(a,b)*pleq NRightarrow max(a,b)leq dfrac {N}{p})因为a,b都为整数,所以(max(a,b)leq lfloordfrac {N}{p}
floor),于是就要知道小于p的互质的数对的个数了,拿出前置芝士中的欧拉函数,于是小于p的数的对数(=2*sum ^{ inylfloordfrac {N}{p}
floor}_{i=1}varphi left( i
ight))(因为如(1,2)和(2,1)同时成立,所以需要乘2),每次都要求自然还是会T,所以需要用到前缀和优化一下.
具体做法
欧拉函数的具体实现:(本人太菜,只会用埃氏筛)
对于x不是质数(varphi(x)=x*prod ^{n}_{i=1}(1-dfrac {1}{p_{i}}))(其中(p_{i})为为x质因数,n为x的质因数的个数)
x为质数时(varphi(x)=x-1),其中十分特殊的(varphi(1)=1).
这样可以直接套入埃氏筛中将所有(1leq xleq N)的(varphi(x))求出,再用一个sum数组统计起来.
如果还不是很了解可以康康例题.
代码
#include<bits/stdc++.h>
#define rap(i,first,last) for(int i=first;i<=last;++i)
using namespace std;
const int maxN=1e7+5;
int N;
double phi[maxN];
bool boo[maxN];
long long sum[maxN];//注意开long long
int main()
{
scanf("%d",&N);
rap(i,1,N)
{
boo[i]=1;
phi[i]=i;//先赋值为i方便处理
}
boo[1]=0;//不是质数
rap(i,2,N)//埃氏筛的部分
if(boo[i])
{
phi[i]=i-1;
rap(j,2,N/i)
{
boo[i*j]=0;
phi[i*j]*=1.0-1.0/i;//求出欧拉函数的值
}
}
sum[1]=1;//1时因为只有(1,1)所以不用乘二
rap(i,2,N)
sum[i]=sum[i-1]+1ll*((int)phi[i])*2;//用前缀和优化
long long answer=0;//注意long long
rap(i,2,N)
if(boo[i])answer+=sum[N/i];//把每个质数所带来的(a,b)全部相加
printf("%lld",answer);//输出answer
return 0;
}
数论题的题解好难写