2019.8.23 Za [数论]

这个博客海星！！从学长的OVO里扒出来的https://www.cnblogs.com/meowww/p/6400841.html

CQOI2007 余数求和

给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值
其中k mod i表示k除以i的余数。
例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

懒得看证明啊.... 再说吧... (from lyd的书)

int main(){
	rd(n),rd(k);ans=n*k;
	for(int x=1,gx;x<=n;x=gx+1){
		gx=k/x?Min(k/(k/x),n):n;
		ans-=(k/x)*(x+gx)*(gx-x+1)/2;
	}
	printf("%lld",ans);
	return 0;
}

欧拉函数

笔记见笔记本上吧...
关于欧拉函数的性质还有积性函数的一些知识

(varphi(N)=N*frac {p_1-1}{p_1}*frac{p_2-1}{p_2}*...*frac{p_m-1}{p_m}=prodlimits_{质数p|N}(1-frac1p))

int phi(int n){
	int ans=n;
    for(int i=1;i<=sqrt(n);++i)
        if(!n%i){
			ans=ans/i*(i-1);
            while(!n%i) n/=i;
    }
    if(ans>1) ans=ans/n*(n-1);
}

利用Eratosthenes筛法的思想在(O(N\,log\,N))求出(2sim N)中每个数的欧拉函数

void euler(int n){
	for(int i=2;i<=n;++i) phi[i]=i;
    for(int i=2;i<=n;++i)
        if(phi[i]==i)
            for(int j=i;j<=n;j+=i)
                phi[j]=phi[j]/i*(i-1);
}

线性筛的思想 (O(N))得出(2sim N)每个数的欧拉函数

int v[N],prime[N],phi[N];
void euler(int n){
	memset(v,0,sizeof(v));
    m=0;
    for(int i=2;i<=n;++i){
		if(!v[i]) v[i]=i,prime[++m]=i,phi[i]=i-1;
   		for(int j=1;j<=m;++j){
			if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j],
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
    }
}

[POJ3090]Visible Lattice Points

当钉子坐标为((x,y))时当且仅当(1le x,yle N,x e y并且gcd(x,y)=1)时

答案即是(3+2*sumlimits_{i=2}^Nvarphi(i))

这个题有个升维的版本即NNN的图有个人用莫比乌斯反演证明！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1500,M=150+5,inf=0x3f3f3f3f,P=19650827;
int n,mx=1005,sum[N];
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

int v[N],prime[N],cntp,phi[N];
void euler(){
	memset(v,0,sizeof(v)),cntp=0;
	for(int i=2;i<=mx;++i){
		if(!v[i]) v[i]=i,prime[++cntp]=i,phi[i]=i-1;
		for(int j=1;j<=cntp;++j){
			if(prime[j]>v[i]||prime[j]>mx/i) break;
			v[i*prime[j]]=prime[j],
			phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
		}
	}
}

int main(){
	freopen("in2.txt","r",stdin);
	//freopen("xor.out","w",stdout);
	euler();sum[1]=0;
	for(int i=2;i<=mx;++i) sum[i]=sum[i-1]+phi[i];
	int T;rd(T);
	for(int i=1;i<=T;++i) rd(n),printf("%d %d %d
",i,n,3+(sum[n]<<1));
	return 0;
}