@KirinBill
2017-10-12T12:44:29.000000Z
字数 11726
阅读 1146
学习笔记
数论
感觉这个东西很需要感觉,要多练习。。。
目录
定义整数域上的数论函数:
这个函数就是莫比乌斯函数。
性质
代码:
#include <cstdio>
#include <cmath>
using std::sqrt;
using std::floor;
const int INF=2e9,MAXN=50005;
int miu[MAXN];
long long sqr[MAXN];
inline void Euler_miu(){
static int prm[MAXN];
static bool notP[MAXN];
notP[1]=true,miu[1]=1;
for(int i=2;i<MAXN;++i){
if(!notP[i]){
prm[++prm[0]]=i;
miu[i]=-1;
}
for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
tmp=i*prm[j];
notP[tmp]=true;
if(i%prm[j]==0){
miu[tmp]=0;
break;
}
else miu[tmp]=-miu[i];
}
}
}
inline void pre_tab(){
for(int i=1;i<MAXN;++i)
sqr[i]=(long long)i*i;
}
inline int cal(int r){
long long ret=0;
for(int i=1,lim=floor(sqrt(r));i<=lim;++i)
ret+=r/sqr[i]*miu[i];
return ret;
}
inline int bin_chop(int k){
int l=1,r=INF;
long long mid;
while(l<=r){
mid=(long long)l+r>>1;
if(cal(mid)>=k) r=mid-1;
else l=mid+1;
}
return l;
}
int main(){
Euler_miu();
pre_tab();
int T;
scanf("%d",&T);
int k;
while(T--){
scanf("%d",&k);
printf("%d\n",bin_chop(k));
}
return 0;
}
对于两个函数,若是的狄利克雷前缀和,即:,则有如下结论:
形式一:
形式二:
应用方法
#include <cstdio>
#include <algorithm>
using std::min;
const int MAXN=50005;
int miu[MAXN],sum[MAXN];
inline void Euler_miu(){
static int prm[MAXN];
static bool notP[MAXN];
notP[1]=true,miu[1]=1;
for(int i=2;i<MAXN;++i){
if(!notP[i]){
prm[++prm[0]]=i;
miu[i]=-1;
}
for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
tmp=i*prm[j];
notP[tmp]=true;
if(i%prm[j]==0){
miu[tmp]=0;
break;
}
else miu[tmp]=-miu[i];
}
}
}
inline void pre_sum(){
Euler_miu();
for(int i=1;i<MAXN;++i)
sum[i]=sum[i-1]+miu[i];
}
inline int cal(int n,int m){
int ret=0;
for(int i=1,lim=min(n,m),r;i<=lim;i=r+1){
r=min(n/(n/i),m/(m/i));
if(r>lim) r=lim;
ret+=(sum[r]-sum[i-1])*(n/i)*(m/i);
}
return ret;
}
inline int solve(int a,int b,int c,int d,int k){
--a,--c;
a/=k,b/=k,c/=k,d/=k;
return cal(b,d)-cal(b,c)-cal(a,d)+cal(a,c);
}
int main(){
pre_sum();
int n;
scanf("%d",&n);
int a,b,c,d,k;
while(n--){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
printf("%d\n",solve(a,b,c,d,k));
}
return 0;
}
#include <cstdio>
const int MAXN=1e7+5;
int prm[MAXN],miu[MAXN];
inline void Euler_miu(int n){
static bool notP[MAXN];
notP[1]=true,miu[1]=1;
for(int i=2;i<=n;++i){
if(!notP[i]){
prm[++prm[0]]=i;
miu[i]=-1;
}
for(int j=1,tmp;j<=prm[0] && i*prm[j]<=n;++j){
tmp=i*prm[j];
notP[tmp]=true;
if(i%prm[j]==0){
miu[tmp]=0;
break;
}
else miu[tmp]=-miu[i];
}
}
}
int main(){
int n;
scanf("%d",&n);
Euler_miu(n);
long long ans=0;
for(int i=1;i<=prm[0];++i){
for(int j=prm[i],k=1,tmp;j<=n;j+=prm[i],++k){
tmp=n/j;
ans+=(long long)miu[k]*tmp*tmp;
}
}
printf("%lld",ans);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
using std::min;
using std::sort;
const int MAXQ=2e4+5,MAXN=1e5+5;
int miu[MAXN];
struct data{
int id;
long long c;
friend bool operator< (const data &a,const data &b){
return a.c<b.c;
}
}sgm[MAXN];
struct query{
int id,n,m,a,ans;
static bool cmp_a(const query &a,const query &b){
return a.a<b.a;
}
static bool cmp_id(const query &a,const query &b){
return a.id<b.id;
}
}qry[MAXQ];
class BIT{
private:
unsigned c[MAXN];
int lowbit(int x){return x&-x;}
unsigned qry(int r){
unsigned ret=0;
for(;r;r-=lowbit(r))
ret+=c[r];
return ret;
}
public:
void add(int l,unsigned x){
for(;l<MAXN;l+=lowbit(l))
c[l]+=x;
}
unsigned qry(int l,int r){
return qry(r)-qry(l-1);
}
}ta;
inline void Euler_sv(){
static int prm[MAXN];
static long long dProd[MAXN],prodS[MAXN];
static bool notP[MAXN];
notP[1]=true,miu[1]=sgm[1].c=1;
for(int i=2;i<MAXN;++i){
if(!notP[i]){
prm[++prm[0]]=i;
dProd[i]=i,prodS[i]=1+i;
miu[i]=-1,sgm[i].c=1+i;
}
for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
tmp=i*prm[j];
notP[tmp]=true;
if(i%prm[j]==0){
dProd[tmp]=dProd[i]*prm[j];
prodS[tmp]=prodS[i]+dProd[tmp];
miu[tmp]=0,sgm[tmp].c=sgm[i].c/prodS[i]*prodS[tmp];
break;
}
else{
dProd[tmp]=prm[j];
prodS[tmp]=1+prm[j];
miu[tmp]=-miu[i],sgm[tmp].c=sgm[i].c*sgm[prm[j]].c;
}
}
}
}
inline unsigned cal(int n,int m){
unsigned ret=0;
for(int l=1,r,lim=min(n,m);l<=lim;l=r+1){
r=min(n/(n/l),m/(m/l));
if(r>lim) r=lim;
ret+=(unsigned)(n/l)*(m/l)*ta.qry(l,r);
}
return ret;
}
int main(){
Euler_sv();
for(int i=1;i<MAXN;++i)
sgm[i].id=i;
sort(sgm+1,sgm+MAXN);
int q;
scanf("%d",&q);
for(int i=1;i<=q;++i){
scanf("%d%d%d",&qry[i].n,&qry[i].m,&qry[i].a);
qry[i].id=i;
}
sort(qry+1,qry+q+1,query::cmp_a);
for(int i=1,j,k=1;i<=q;++i){
for(;sgm[k].c<=qry[i].a;++k){
for(j=1;j*sgm[k].id<MAXN;++j)
ta.add(j*sgm[k].id,(unsigned)miu[j]*sgm[k].c);
}
qry[i].ans=cal(qry[i].n,qry[i].m)&INT_MAX;
}
sort(qry+1,qry+q+1,query::cmp_id);
for(int i=1;i<=q;++i)
printf("%d\n",qry[i].ans);
return 0;
}
#include <cstdio>
#include <algorithm>
using std::min;
const int MAXN=1e7+5,P=20101009;
int inv_6;
int miu[MAXN],tab[MAXN];
inline void Euler_miu(){
static int prm[MAXN];
static bool notP[MAXN];
notP[1]=true,miu[1]=1;
for(int i=2;i<MAXN;++i){
if(!notP[i]){
prm[++prm[0]]=i;
miu[i]=-1;
}
for(int j=1,tmp;tmp=i*prm[j],j<=prm[0] && tmp<MAXN;++j){
notP[tmp]=true;
if(i%prm[j]==0){
miu[tmp]=0;
break;
}
else miu[tmp]=-miu[i];
}
}
}
inline void pre_tab(){
Euler_miu();
for(int i=1;i<MAXN;++i)
tab[i]=(tab[i-1]+(long long)i*i*miu[i]%P+P)%P;
for(int i=2;i<MAXN;++i)
miu[i]+=miu[i-1];
}
inline int sum(int n,int m){
return (long long)((long long)n*(n+1)>>1)%P*(((long long)m*(m+1)>>1)%P)%P;
}
inline int cal(int n,int m){
int ret=0;
for(int l=1,r,lim=min(n,m);l<=lim;l=r+1){
r=min(n/(n/l),m/(m/l));
if(r>lim) r=lim;
ret=(ret+(long long)(tab[r]-tab[l-1]+P)%P*sum(n/l,m/l)%P)%P;
}
return ret;
}
int main(){
pre_tab();
int n,m;
scanf("%d%d",&n,&m);
int ans=0;
for(int l=1,r,lim=min(n,m);l<=lim;l=r+1){
r=min(n/(n/l),m/(m/l));
if(r>lim) r=lim;
ans=(ans+(long long)cal(n/l,m/l)*(((long long)(l+r)*(r-l+1)>>1)%P)%P)%P;
}
printf("%d",(ans+P)%P);
return 0;
}
#include <cstdio>
#include <algorithm>
using std::min;
const int MAXN=50005;
int miu[MAXN];
long long tao[MAXN];
inline void Euler_sv(){
static int prm[MAXN],dExp[MAXN];
static bool notP[MAXN];
notP[1]=true,dExp[1]=miu[1]=tao[1]=1;
for(int i=2;i<MAXN;++i){
if(!notP[i]){
prm[++prm[0]]=i;
dExp[i]=1;
miu[i]=-1,tao[i]=2;
}
for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
tmp=i*prm[j];
notP[tmp]=true;
if(i%prm[j]==0){
dExp[tmp]=dExp[i]+1;
miu[tmp]=0;
tao[tmp]=tao[i]/(dExp[i]+1)*(dExp[tmp]+1);
break;
}
else{
dExp[tmp]=1;
miu[tmp]=-miu[i];
tao[tmp]=tao[i]*tao[prm[j]];
}
}
}
}
inline void pre_tab(){
Euler_sv();
for(int i=2;i<MAXN;++i){
miu[i]+=miu[i-1];
tao[i]+=tao[i-1];
}
}
inline long long cal(int n,int m){
long long ret=0;
for(int l=1,r,lim=min(n,m);l<=lim;l=r+1){
r=min(n/(n/l),m/(m/l));
if(r>lim) r=lim;
ret+=(long long)tao[n/l]*tao[m/l]*(miu[r]-miu[l-1]);
}
return ret;
}
int main(){
pre_tab();
int T;
scanf("%d",&T);
int n,m;
while(T--){
scanf("%d%d",&n,&m);
printf("%lld\n",cal(n,m));
}
return 0;
}