首页 > > 程序设计 > C/C++ >

数论题总结

2018-06-17 22:55:23来源：未知 阅读 ()

新老客户大回馈,云服务器低至5折

　　这几天做了几道微不足道的数论题，感觉做法都十分的高啊，我这种僵化的思想是很难有那样的切题知识水平的。然后做了几道题，感觉也有点熟悉数学的那一套理论了，虽然我还是太弱，但是有点东西还是要讲出来的嘛，一起谈笑风生，积累人生经验。闷声发大财虽然好，但是是不支持的。

　　上面那句话看不懂就无视吧。

　　那么对于数论题，我们应该如何下手呢？？我总结了一些分析技巧和优化技巧，希望有用(希望考场推得出来)。

题目分析：

1.题目给的很直接了，让你求这个那个。

　　以两道同年的NOI题目为例。

　　1.荒岛野人 Savage

　　　　反正不管怎么样，看完题目我就知道考什么了(这并不能掩饰我WA几次的事实)。一眼扩展欧几里得，数据规模也当然很支持。暴力枚举m，n2扩欧就能跑过，速度较西方记者而言也不遑多让。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const int N = 21;
int n,m,c[N],p[N],l[N];
inline int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
inline int Abs(int x){return x>0?x:-x;}
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline void exgcd(int a,int b,int &x,int &y)
{
  if(b==0){x=1;y=0;return;}
  exgcd(b,a%b,y,x);y-=a/b*x;
}
inline bool check(int i,int j,int cir)
{
  int A=(p[i]-p[j]),B=cir,C=(c[j]-c[i]),X=0,Y=0;
  int d=gcd(A,B);if(C%d!=0)return true;
  exgcd(A,B,X,Y);B=Abs(B/d);
  X=((X/d*C)%B+B)%B;if(X==0)X+=B;
  return X>min(l[i],l[j]);
}
int main()
{
  n=gi();
  for(int i=1;i<=n;++i)
    c[i]=gi(),p[i]=gi(),l[i]=gi(),m=max(m,c[i]);
  for(;;++m)
    {
      int flag=1;
      for(int i=1;i<=n;++i)
    	for(int j=i+1;j<=n;++j)
	     if(!check(i,j,m))
	        {flag=0;i=n+1;break;}
      if(flag)break;
    }
  printf("%d",m);
  return 0;
}

 

 

　　2.机器人m号 robot

　　　　　　　讲真我认为应该批判一番这个出题人，本来考场时间就不多，还花个10分钟看题，还要记住什么军人学者政客(噫,怎么这么像他)。

　　 独立数就是欧拉函数嘛，至于按因子数分类什么的跟莫比乌斯函数关系并不(没)大(有)。然后求出军人政客后用欧拉函数的性质求出学者的个数就可以了。

　　 这题做法还是比较神的。欧拉函数不是是积性的嘛，它又是给你的质数因子，所以你利用积性+乘法结合律，就可以写出一个二维DP的式子。但有一个更加高的方法就是直接把答案带进去递推，相当于用那个DP式子的分奇偶前缀和直接算，数组都不用开。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const LL Mod = 10000;
LL Ans1,Ans2,m,k;
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void pL(LL x)
{
  if(x<0)putchar('-'),pL(-x);
  if(x<10)putchar(x+'0');
  else pL(x/10),putchar(x%10+'0');
}
void pc(){putchar('\n');}
LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
LL Qpow(LL d,LL z)
{
  LL ans=1;
  for(;z;z>>=1,d=d*d%Mod)if(z&1)ans=ans*d%Mod;
  return ans;
}
int main()
{
  k=gL();m=1;
  for(LL i=1;i<=k;++i)
    {
      LL p=gL(),e=gL();
      m=m*Qpow(p,e)%Mod;
      if(p==2)continue;
      LL ans1=(Ans1+(Ans2+1)*(p-1))%Mod;
      LL ans2=(Ans2+Ans1*(p-1))%Mod;
      Ans1=ans1;Ans2=ans2;
    }
  pL(Ans2);pc();pL(Ans1);pc();pL(((m-Ans1-Ans2-1)%Mod+Mod)%Mod);
  return 0;
}

 

 

 

　　2.公式推导

　　题目给了你一个公式，但是直接算是显然会T的，这个时候就要将公式等价化简。这种题目SDOI以前是有的，现在他们的Oier身经百战了，见的多了，这种问题就没怎么出现过了。但对于新手来说，对于对数论函数的高妙使用的熟悉还是有很大帮助的。

　　1.Longge的问题

你看，多么简单的一个问题，但显然暴力是跑不过去的，这点上不管是香港记者还是松爷也必须承认的。

那么我们必须考虑优化(不是底层优化！)。注意到有贡献的只有gcd，且关于gcd有一个优美的性质：gcd(a/gcd(a,b),b/gcd(a,b))=1；

就是说除了gcd之后两个数忽然就互质了，于是个数就是欧拉那么多个。

于是答案就是sigma(d|n) d*phi(n/d)；phi在线爆算就可以了。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
LL n,Ans;
LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
LL get(LL x)
{
  LL ans=x;
  for(LL i=2;i*i<=x;++i)
    if(x%i==0)
      {
    ans=ans/i*(i-1);
    while(x%i==0)x/=i;
      }
  if(x!=1)ans=ans/x*(x-1);
  return ans;
}
int main()
{
  n=gL();
  for(LL i=1;i*i<=n;++i)
    if(n%i==0)
      {
    if(i*i==n)Ans+=i*get(i);
    else Ans+=(i*get(n/i)+(n/i)*get(i));
      }
  printf("%lld\n",Ans);
  return 0;
}

 

 

 

 

 

 

 

 

 

2.GCD

这问的问题啊，还是太简单，太幼稚。

一个数对(x,y)的gcd为质数p，如果假设x>y，那么对于(x/p,y/p)而言答案就是很水的类似于上一题的操作了。

对于所有的数，我们用前缀和优化一下就可以了，答案再乘以2加上1就可以了。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define Inc i*Prime[j]
using namespace std;
const int N = 10010000;
int n,Prime[N],tot,ph[N],vis[N];
LL Q[N],Ans;
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
LL gl()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void prepare()
{
  ph[1]=1;
  for(int i=2;i<=n;++i)
    {
      if(!vis[i]){Prime[++tot]=i;ph[i]=i-1;}
      for(int j=1;j<=tot;++j)
    {
      if(Inc>N)break;vis[Inc]=1;
      if(i%Prime[j])ph[Inc]=ph[i]*ph[Prime[j]];
      else{ph[Inc]=ph[i]*Prime[j];break;}
    }
    }
  for(int i=2;i<=n;++i)
    Q[i]=Q[i-1]+(LL)ph[i];
}
int main()
{
  n=gi();prepare();
  for(int i=1;i<=tot;++i)
    Ans+=(2*(Q[n/Prime[i]])+1);
  printf("%lld",Ans);
  return 0;
}

 

 

 

 

 

 

 

　　3.构建数学模型，巧妙转化

　　这部分是最难的。就像数学原理人人都会，但数学题不见得人人都会做；谁都有过冲动，但有的人非要去肛坦克。一般碰到这种题目，不应及时下手，应该在草稿纸上理性分析，并且打好暴力验证你的思想。学长传授的人生经验是，推一个式子打一遍，不要在过程中出现偏差。

1.仪仗队

这道题简直就是莫比乌斯反演的弱化版(第一象限)的弱化版(n=m)的弱化版(n<=40000)好吗！真的不怕考场上有人打表吗？

反正一个点能被看到就是这个点横纵坐标的gcd=1才可以！你再只看一个上或者下三角，就是欧拉函数！水的一笔。

/**************************************************************
    Problem: 2190
    User: Ryze
    Language: C++
    Result: Accepted
    Time:24 ms
    Memory:1760 kb
****************************************************************/
 
#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define Inc i*Prime[j]
using namespace std;
const int N = 40100;
int n,vis[N],Prime[N],ph[N],tot,Ans;
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void pui(int x)
{
  if(x<10)putchar(x+'0');
  else pui(x/10),putchar(x%10+'0');
}
void shai()
{
  ph[1]=1;
  for(int i=2;i<=n;++i)
    {
      if(!vis[i]){Prime[++tot]=i;ph[i]=i-1;}
      for(int j=1;j<=tot;++j)
    {
      if(Inc>n)break;vis[Inc]=1;
      if(i%Prime[j])ph[Inc]=ph[i]*ph[Prime[j]];
      else {ph[Inc]=ph[i]*Prime[j];break;}
    }
      Ans+=ph[i];
    }Ans-=ph[n]-1;
}     
int main()
{
  n=gi();shai();
  printf("%d",Ans*2+1);
  return 0;
}

 

 

 

 

2.古代猪文

　　题面是很有趣的，充满着批判的意味，仿佛是要弄出一个大新闻，让人Excited！

　　在PKU的学长跟我们讲这是板子合集，前提是你要看出来。

　　题目显然求G的sigma{d|n}(一个组合数)次方。组合数之和做指数肯定是不支持的。因为模数是个质数，就把指数模一个phi(模数)=模数-1;又因为模数-1是个合数，且发现没有相同质因子，就用扩展Lucas来敲。然后再打一个快速幂就可以AC这道牛逼哄哄的题目惹。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const LL Mod = 999911659;
const int N = 50010;
LL n,g,M[]={0,2ll,3ll,4679ll,35617ll},Y[10];
LL J[N],A[N],Z[10];
void pL(LL x)
{
  if(x<10)putchar(x+'0');
  else pL(x/10),putchar(x%10+'0');
}
LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void prepare(LL x)
{
  A[1]=J[0]=J[1]=1;
  for(LL i=2;i<x;++i)
    J[i]=J[i-1]*i%x,A[i]=((-(x/i)*A[x%i])%x+x)%x;
}
LL C(LL N,LL M,LL P)
{
  if(N<M)return 0ll;
  LL ans=J[N];
  ans*=A[J[M]];ans%=P;
  ans*=A[J[N-M]];ans%=P;
  return ans;
}
LL Lucas(LL N,LL M,LL P)
{
  if(!M)return 1ll;
  if(N<P&&M<P)return C(N,M,P);
  LL c=C(N%P,M%P,P);if(!c)return 0ll;
  LL L=Lucas(N/P,M/P,P);return c*L%P;
}
LL get(LL mod)
{
  LL ans=0;
  for(LL i=1;i*i<=n;++i)
    if(n%i==0)
      {
 　　   ans+=Lucas(n,i,mod);ans%=mod;
  　　  if(i*i!=n)ans+=Lucas(n,n/i,mod),ans%=mod;
      }
  return ans;
}
LL Qpow(LL d,LL z)
{
  LL ans=1;
  for(;z;z>>=1,d=d*d%Mod)if(z&1)ans=ans*d%Mod;
  return ans;
}
int main()
{
  n=gL();g=gL()%Mod;
  if(g==0){pL(0);return 0;}
  for(int t=1;t<=4;++t)
    {
      prepare(M[t]);
      Y[t]=get(M[t]);
      Z[t]=((Mod-1)/M[t])*A[((Mod-1)/M[t])%M[t]];
      Y[0]+=Y[t]*Z[t]%(Mod-1);Y[0]%=(Mod-1);
    }
  return pL(Qpow(g,Y[0])),0;
}

 

 

 

3.圆上的整点

　　这题真是神了系列。

　　首先你会想到a^2+b^2=r^2之枚举a看b。现在我们来想想优化。

　　a^2+b^2=r^2；

　　a^2=r^2-b^2；

　　a^2=(r+b)(r-b)；

　　令d = gcd(右边)；　　// 神奇思想。左式为完全平方数，就在右边构建完全平方数。

　　a^2=d^2*[(r+b)/d]*[(r-b)/d]；

　　因为右边是完全平方数，两中括号内的数互质，所以本身就是完全平方数。

　　令其分别为p^2,q^2；

　　则有： p^2+q^2=2r/d；

　　所以你就可以直接枚举了。枚举d,再枚举p或者q就好。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <cstring>
#include    <cmath>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
#define fa (x >> 1)
#define MID  LL mid=(l+r)>>1
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
LL Ans,r,R,p,q,A,B,X,Y,d;
LL gi()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9' || ch<'0'){if(ch=='-')res=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
  return x*res;
}
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
int main()
{
  R=gi();r=2*R;
  for(d=1;d<=sqrt(r);++d)
    {
      if(r%d==0)
        {
	  LL K1=r/d;K1/=2;K1=sqrt(K1);
	  for(q=1;q<K1;++q)
            {
	      p=sqrt(r/d-q*q);
	      if(p*p+q*q==r/d)
                {
		  A=p*p;B=q*q;
		  if(gcd(A,B)!=1 || A==B)continue;
		  else Ans++;
                }
            }
	  LL K2=d;K2/=2;K2=sqrt(K2);
	  for(q=1;q<=K2;++q)
            {
	      p=sqrt(d-q*q);
	      if(p*p+q*q==d)
                {
		  A=p*p;B=q*q;
		  if(gcd(A,B)!=1 || A==B)continue;
		  else Ans++;
                }
            }
        }
    }
  cout<<4*Ans+4;
}

 

 

 

 

优化技巧

1.数论分块。

　　我们经常推公式推出来一个关于“取下整”的东西。其实这就是我们分块优化的突破口。

　　打一个表，我们可以发现，[n/i]取下整这种东西的取值并不多，有很多连续的一段其实都是一个值。经过严谨的证明，大概有2√n个。

　　这个时候公式就可能可以得到简化。我们用前缀和维护一下，在一段相同取值的块内把整块求出来，然后直接跳到下一个块去。

　　公式是：

　　　　初始化：l=1,r;

　　　　分块操作：r=n/(n/l);

　　　　下一块：l=r+1;

　　这便是套路所在。有此分块，O(n)的复杂度就被缩成了O(sqrt(n))；数论分块在莫比乌斯和数论中应用十分广泛，考点也很多。

下面有一道经典的数论分块题目，涉及到分块后的不同操作，推荐一下：

模积和

 

这里放白字题解：

　　在此我们先了解正整数意义下的模运算，叫做取余运算。

　　n%p 可以用式子 n-(n/p)*p 来等效替代(仅限于整型)。

　　所以原式可以化简，具体式子我就给一神犇学长的博客。他推的比我的清楚，而且里面有套路。

　　所以接下来的就是喜闻乐见的各种分块。注意一定要一步一模。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const LL Mod = 19940417;
LL n,m,Ans;
LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
inline LL sum(LL l,LL r){return (r-l+1)*(r+l)/2%Mod;}
inline LL Sum(LL x){return x*(x+1)%Mod*(2*x+1)%Mod*3323403%Mod;}
inline LL calc(LL A)
{
  LL ret=0;
  for(LL l=1,r;l<=A;l=++r)
    {
      r=A/(A/l);
      ret+=(r-l+1)*A%Mod-(A/l)*sum(l,r)%Mod;
      ret=(ret%Mod+Mod)%Mod;
    }
  return ret;
}
LL cal(LL A)
{
  LL res=0;
  for(int l=1,r;l<=n;l=++r)
    {
      r=min(n/(n/l),m/(m/l));
      LL ans1=n*m%Mod*(r-l+1)%Mod;
      LL size=((Sum(r)-Sum(l-1))%Mod+Mod)%Mod;
      LL ans2=(n/l)*(m/l)%Mod*size%Mod;
      LL ans3=n*(m/l)%Mod*sum(l,r)%Mod;
      LL ans4=m*(n/l)%Mod*sum(l,r)%Mod;
      res=((res+ans1+ans2-ans3-ans4)%Mod+Mod)%Mod;
    }
  return res;
}
int main()
{
  n=gL();m=gL();if(n>m)swap(n,m);
  LL ans1=calc(n),ans2=calc(m);
  Ans=ans1*ans2%Mod;
  LL ans3=cal(n);Ans=(Ans-ans3)%Mod;
  printf("%lld\n",(Ans+Mod)%Mod);
  return 0;
}

 2.未完待续... ...

 

 

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：顺序线性表之大整数求和C++实现

下一篇：C++ 拷贝控制和资源管理，智能指针的简单实现

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签