蒟蒻的数论

弱鸡的初等数论笔记

整除(小学奥数内容)

  有关性质:
传递性、同乘性、以及部明明显的质量。

       
还有b|0对于全部b≠0成立。

       
试着证喜宝(Hipp)下:若(a,b)=1,a|n,b|n,则(ab)|n;

 

 

 相关姿势:求出x的具有因子。那个应该都会吗。应该没有更好的复杂度了。

void getd(int x)
{
    for(int i=1;i*i<=x;++i)
        if(x%i==0)
            {
                d[++tot]=i;
                if(i*i!=x)d[++tot]=x/i;
            }
    //sort(d+1,d+tot+1);
}

  

 

 

 

余数和同余(小学奥数内容)

  定义;模意义;

  有关性质:传递性、同加减乘,差异除,以及部分显著的天性。

       试着表明一下:a%p=x,a%q=x,(p,q)=1
  =>   a%(pq)=x;

              尝试用到地点的定律。

  快速幂,龟速乘等等;

  

  中华人民共和国剩余定理;

  相关难点:

    某校内OJ1272   
 就是板子对吧。

    HDU1788
      思维不要江僵化了。

 

 

 

 

 

 

 

 

至于难点:

  1.codevs1455路径

    一些小拍卖就足以啊。

 

 

 

 

 

 

  2.膜法数字:

    n个数中必定含有1,2,3,4三个数字。求一种排列情势使其膜7为0(显著的SPJ)。

    思考一下:音讯学最要紧的二种沉思是怎么样?

    那大概江会是你们前几天最大的获取!

 

大胆猜想
不用证明
打表输出

 

 

 

 

 

 

 

 

 

 

 

素数与合数

  定理;1都不是;2是绝无仅有的偶质数。

  筛法:素数的线性筛法。

  分解质因子;spqt(n);

  判定:对于小数,sqrt(n);  

     对于大数,非完美算法
miller-rabin;对于(a,p)=1,有:

         费马小定理:如果p是质数,那么a^(p-1)≡1(mod
p);

           你会意识那远远不够,比如说561=3*11*17,1105=5*13*17,但无论如何它们都… 

         补充定理:假使p是质数,那么a*a≡1(mod
p)的解只有a=1或p-1。试用初级中学数学申明。

              起初有点思维推导了。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <ctime>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
int n;
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;
}
int Qpow(int d,int z,int mod)
{
  int ans=1;
  for(;z;z>>=1,d=d*d%mod)
    if(z&1)ans=ans*d%mod;
  return ans;
}
bool check(int a,int n,int t,int u)
{
  int x=Qpow(a,u,n);
  while(t--)
    {
      int y=x*x%n;
      if(y==1 && x!=1 && x!=n-1)
    return true;
      x=y;
    }
  return x!=1;
}
// check: return [n must not be a prime];
bool Mr(int n)
{
  if(n==1)return false;
  if(n==2||n==3||n==5||n==7||n==11)return true;
  if(n==4||n==6||n==8||n==9||n==10)return false;
  int m=n-1,j=0;
  while(!(m&1))m>>=1,++j; //n=1+m*2^j
  for(int t=1;t<=10;++t)   //judge 10 times
    {
      int a=rand()%(n-2)+1;
      if(check(a,n,j,m))return false;
    }
  return true;
}
int main()
{
  srand(time(NULL));
  n=gi(),printf("%s\n",Mr(n)?"Yes":"No");
  return 0;    
}

 

 

 

 

 

 

  因数分解;唯一分解定理。

       威尔逊定理。逆定理。

       费马小定理;与欧拉定理之间的涉嫌。(记住欧拉定理就阔以了)。

       因子个数;因子和(其实那几个阔以筛出来);

       求大整数因子算法:Fermat;Pollard
Rho;

 

 

 

 

 

 

 

 

 

乘法逆元

  定义;

  性质(用途);证明;

  求法;单个;线性求(必须是质数);

A[i]=-(p/i)*A[p%i];

 

 

 

 

 

  那题你们应该都做过…
…来自于某年提升组;

  NOIP2012 其实并不希罕那种驾驭就是闭着眼切不通晓就是玩蛋的题

  哦对三行扩充欧几里得代码。明白什么的没供给了。( 反正小编是hh 想看的话网上一大堆)

int exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1;y=0;return a;}
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int main()
{
    int gcd=exgcd(a,b,x,y);
    // 把  ax+by=gcd(a,b)  的解存储在x,y中。
}    

 

   

  乘法逆元是都要会求的,考试场点颇多。数论题和组合数学题很多都要用到它。

 

 

 

 

 

 

 

 

GCD与LCM

  定义;

  性质;i*j=gcd(i,j)*lcm(i,j);

  GCD的求法;LCM的求法;

 

 

看上去不难,但实际上…
…下边来做联合思维题

 

 

【题目名:密码  strongbox】 【64MB】 【4s】
【题目描述】
    有一个密码箱,0—n-1中的某些整数是它的密码。
    满足:如果a和b都是它的密码,那么(a+b)%n也是它的密码(a=b是合法情况)。
    欧洲皇帝QT试了k次密码,前k-1次都失败了,最后一次成功了。
    请问:该密码箱最多可能有多少种不同的密码。
【输入格式】
    输入第一行有两个正整数,分别表示n,k。
    第二行为k个非负整数,表示每次试的密码。
    保证存在合法解。
【输出格式】
    一行一个整数,表示结果。
【输入样例1】
    42 5
    28 31 10 38 24
【输出样例1】
    14
【数据规膜】
    对于10%的数据:n≤10^4,k≤100;
    另有10%的数据:n≤10^9,k≤100;
    另有10%的数据:n≤10^9,k=1;
    对于前60%的数据:k≤1000;
    对于100%的数据:1≤k≤250,000≤n≤10^14;

 

 

这道题确实思维难度颇高。我就把解题报告讲(kuai)一讲(kuai)。
首先你得推出2个东西。
1.如果x是密码,那么gcd(x,n)也是密码。
    具体证明联系"扩展欧几里得"知识。
2.如果x,y是密码,那么gcd(x,y)也是密码。
    具体证明同上。

然后我们对密码进行分析。
记尝试密码集合为a;
1.对于密码集合A,里面所有元素的gcd记作X,有X∈A;
    证明:引理2;
2.X是A中最小的元素,且X|gcd(a[k],n);
    证明:引理2,引理1;
3.其他的元素是2X,3X,4X...⌊n/x⌋*x;
    证明:显而易见;
4.X可能有多个解,但多个解不能同时存在。所以X取解集的最小值。
    证明:引理1,答案要求;
5.X与a[j](1≤j<k)互质;
    证明:显而易见;
6.最后的答案就是⌊n/x⌋;

  

 

具体代码实现步骤是什么呢?
1.读入a后,a[k]=gcd(n,a[k]);
2.a[j]=gcd(a[j],a[k]);
    这是为了方便我们节省复杂度。
3.处理出a[k]的所有因子,制造答案可能集;
4.把所有不符合上述结论的因子删掉;
5.找到最小的答案,并输出。

 

具体代码我就不打了,你们想做也做不了,只能嘴巴一下。
为什么呢?
给你一句伤心的话:
Please contact lydsy2012@163.com!

  

 

 

 

 

 

 

 

欧拉函数及欧拉定理

  欧拉函数:定义;

       性质;积性函数;尝试求出图片 1;

 

 

          计算图片 2图片 3

 

       欧拉函数的线性筛(积性);O(sqrt(n))求单个欧拉函数值。

  欧拉定理;

 

 

 

 

 

 

看题。 

 

  引子:求分母小于等于n的最简真分数的个数。

你以为此处会有代码吗
答案就是

图片 4

不要思维江化了啊

 

 

 

 

 

 

 

 

 

 

  1.BZOJ2705 欧拉函数。所以这是答案

 

#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.
BZOJ2818
 BZOJ2190 所以那两题很水咯。

 

#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;
}

 

#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;
}

 

 

 

 

 

 

 

 

   

 

 

 

 

 

  3.
BZOJ1951 考的可比多,板子合集,还带了有些思维,是道不错的题。  

 

#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;
}

 

 

 

 

 

 

  4. BZOJ1408 提示:积性,结合率,递×。

#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 F[1010][1010],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;
}

 

  

 

 

 

 

 

 

 

 

 

 

 

  最后来道水题放放松。李电出过的题,我们应该都切过。

   BZOJ3884

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
using namespace std;
int n,p;
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(int x)
{
  if(x<0)putchar('-'),pL(-x);
  if(x<10)putchar(x+'0');
  else pL(x/10),putchar(x%10+'0');
}
int Qpow(int d,int z,int Mod)
{
  int ans=1;
  for(;z;z>>=1,d=(LL)d*d%Mod)if(z&1)ans=(LL)ans*d%Mod;
  return ans;
}
int phi(int x)
{
  int Txd=x;
  for(int i=2;i*i<=x;++i)
    if(x%i==0)
      {
        Txd-=Txd/i;
        while(x%i==0)x/=i;
      }
  if(x>1)Txd-=Txd/x;
  return Txd;
}   
int f(int p)
{
  if(p==1)return 0;int x=phi(p);
  return Qpow(2,x+f(x),p);
}
int main()
{
  int T=gi();
  while(T--)pL(f(gi())),putchar('\n');
  return 0;
}

 

 

 

 

 

 

 

 

 

     

原根与离散对数

  先来探望那道题怎么写。

  某校内OJ 1508。求 a^x≡1 (mod
b)。

  当时自个儿做那题时还太naive,今后考虑很不难是吗?

  介绍一下原根和离散对数。(你们随便听听就够了,有点超)

  原根:

    对于一个互质的数a,b,由欧拉定理知,必定期存款在x≤φ(b),使a^x≡1
(mod b);

    x记作a对模m的阶,记作δm(a);(应该是长那个呢)

1^1≡1(modn),1对模n的阶为1;
2^2≡1(mod3),2对模3的阶为2;
5^6≡1(mod7),5对模7的阶为6;
2^3≡1(mod7),2对模7的阶为3;

 

    由此,定义Ordm(a)为使得a^x≡1
(mod m) 的矮小整数解x;

    如果有Ordma=φ(m),则称a是模m的1个原根。**

    作者精通刚刚看完的终将一脸蒙蔽…
…笔者也是。

  原根的关于性质,笔者蒯了一些。

    (1).具有原根的数一定是:2,4,p^n,2(p^n),在这之中p为奇素数。

    (2).m的相当小原根大小是O(m0.25)的。所以有个别东西你枚举就够了(惨疼的教训)。

**    (3).假若模m有原根,那么它有φ(φ(m))个原根。(制止有人出结论题)。**

**  求原根的不二法门:**

你们不是已经知道了吗?

 

 

离散对数

  初等代数中的对数运算,定义若是有ax=b,则称x是以a为底的对数,记作logab;

  在同余关系中也有类似的难题。给定n,a,b,怎么样求解x使ax≡b
(mod n);

  这一难题也被称作离散对数难点。大家只谈谈n为素数的情事。

  先来谈谈暴力如何做?

  由欧拉定理,大家知道0~n-1内必有一解,递推即可,复杂度O(n);

  但如此并不是很好的算法,上面给出一种O(比n小)的算法。

 

 

 

 

 

率先总结出x=0,1,2…m时ax
(mod n)的值。

设ak≡b (mod n);设
k=p*m+q(q<m);枚举p;

对此多少个枚举出的p,ap*m是一定且可求的。

则足以改写成: ap\*m+qb (mod n);

   继续改: aq*apm≡b (mod n);**

*   再一步: aq\(am)pb (mod n);**

   设T=(am)p,就有:

*        T\aqb (mod n);**

   你就足以用exgcd求出T;

   那么难题就在于求q上。聪明的你能够用很各类措施化解这么些标题。。。

   这种分块用基本不等式算出m取到sqrt(n)时复杂度最卓绝。。。

 

 

 

 

练习题:

  BZOJ2956 模积和;

  BZOJ1407 Savage(NOI 二〇〇二荒岛野人);

  NOIP二〇一四 Day2T3 解方程,同BZOJ2742
Akai的数学作业;

  神题之圆上的整点;

  神题之数论之神CJK;

  其实上边的题材自身一个都不会。

一 、二零零五飞银行职员配对(二分图最大匹配)

  题意:每一架飞机都不可能不要有能够相互同盟的英籍飞行员和外国国籍飞银行人士同盟。给出m个外国国籍飞银行人士,n-m个英籍飞银行人士,以及能够相互协作的外国国籍和英籍飞银行人员,求最多能出动多少飞机。

  思路:二分图最大匹配。

图片 5图片 6

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 int n, m;
 7 const int maxn = 210;//x集合和y集合总最大的点数
 8 bool mp[maxn][maxn];//1表示该ij可以匹配
 9 int cx[maxn];//记录x集合中匹配的y元素是哪一个
10 int cy[maxn];//记录y集合中匹配的x元素是哪一个
11 int vis[maxn];//标记该顶点是否访问过
12 int cntx;
13 bool dfs(int u)
14 {
15     for (int v = m+1; v <= n; v++)
16     {
17         if (mp[u][v] && !vis[v])
18         {
19             vis[v] = 1;
20             if (cy[v] == -1 || dfs(cy[v]))//)//如果y集合中的v元素没有匹配或者是v已经匹配,但是从cy[v]中能够找到一条增广路
21             {
22                 cx[u] = v; cy[v] = u;
23                 return 1;
24             }
25         }
26     }
27     return 0;
28 }
29 int maxmatch()//匈牙利算法主函数
30 {
31     int ans = 0;
32     memset(cx, 0xff, sizeof cx);//初始值为-1表示两个集合中都没有匹配的元素!
33     memset(cy, 0xff, sizeof cy);
34     for (int i = 1; i <= m; i++)
35         if (cx[i] == -1)//如果i未匹配
36         {
37             memset(vis, 0, sizeof(vis));
38             ans += dfs(i);
39         }
40     return ans; 
41 }
42 
43 int main()
44 {
45     while (~scanf("%d%d", &m, &n))
46     {
47         memset(mp, 0, sizeof(mp));
48         int a, b;
49         while (scanf("%d%d", &a, &b))
50         {
51             if (a == -1 && b == -1)break;
52             mp[a][b] = mp[b][a] = 1;
53         }
54 
55         int ans = maxmatch();
56         if(ans>0)printf("%d\n", ans);
57         else printf("No Solution!\n");
58 
59     }
60 
61     return 0;
62 }

View Code

贰 、1459
迷宫游戏(最短路变形)

  思路:给出三个迷宫,迷宫每一种房间都有贰个分数。未来亟待在确认保障从源点到顶点路径最短(消耗费时间间至少)的情景下,使得经过的屋子的分数总和最大。

  思路:SPFA,同时记录分数的转移。

图片 7图片 8

  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<queue>
  5 #include<vector>
  6 #include<map>
  7 using namespace std;
  8 int n, m, st, ed, sum;
  9 const int maxn = 510;
 10 const int maxv = 700;
 11 const int INF = 0x3f3f3f3f;
 12 map<int, int>score;
 13 struct node
 14 {
 15     int to;
 16     int cost;
 17     node(int tt = 0, int cc = 0) :to(tt), cost(cc)
 18     {
 19     }
 20 };
 21 vector<node>mp[maxn];
 22 int cnt[maxn];
 23 int pre[maxn];
 24 int dis[maxn];
 25 bool vis[maxn];
 26 int value[maxn];
 27 bool SPFA()
 28 {
 29     queue<int>q;
 30     memset(cnt, 0, sizeof(cnt));
 31     memset(vis, 0, sizeof(vis));
 32     memset(value, 0, sizeof(value));
 33 
 34     for (int i = 0; i < n; i++)
 35     {
 36         pre[i] = st;
 37         dis[i] = INF;
 38     }
 39     dis[st] = 0;
 40     vis[st] = true;
 41     cnt[st]++;
 42     q.push(st);
 43     value[st] = score[st];
 44     while (!q.empty())
 45     {
 46         int u = q.front();
 47         q.pop();
 48         vis[u] = false;
 49         int sz = mp[u].size();
 50         for (int i = 0; i < sz; i++)
 51         {
 52             int v = mp[u][i].to;
 53             int c = mp[u][i].cost;
 54             if (dis[u] + c < dis[v])
 55             {
 56                 dis[v] = dis[u] + c;
 57                 pre[v] = u;
 58                 value[v] =value[u] + score[v];
 59                 if (!vis[v])
 60                 {
 61                     vis[v] = true;
 62                     cnt[v]++;
 63                     q.push(v);
 64                 }
 65             }
 66             else if (dis[u] + c == dis[v])
 67             {
 68                     if (value[v]<value[u] + score[v])
 69                     {
 70                         value[v] = value[u] + score[v];
 71                         pre[v] = u;
 72                         if (!vis[v])
 73                         {
 74                             vis[v] = true;
 75                             cnt[v]++;
 76                             q.push(v);
 77                         }
 78                     }
 79                 
 80             }
 81         }
 82     }
 83     return true;
 84 }
 85 int main()
 86 {
 87     while (~scanf("%d%d%d%d", &n, &m, &st, &ed))
 88     {
 89         score.clear();
 90         for (int i = 0; i < n; i++)
 91         {
 92             int val;
 93             scanf("%d", &val);
 94             score[i] = val;
 95             mp[i].clear();
 96         }
 97         for (int i = 1; i <= m; i++)
 98         {
 99             int u, v, c;
100             scanf("%d%d%d", &u, &v, &c);
101             mp[u].push_back(node(v, c));
102             mp[v].push_back(node(u, c));
103 
104         }
105         SPFA();
106         int minc = dis[ed];
107         int sum = value[ed];
108         printf("%d %d\n", minc, sum);
109     }
110     return 0;
111 }

View Code

三 、1298 圆与三角形(计算几何)

  题意:给出贰个圆和三个三角形,判断他们是否相交。

  思路:数学模拟。

图片 9图片 10

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 struct P
 6 {
 7     double x, y;
 8 };
 9 struct circle
10 {
11     double x, y;
12     double r;
13 };
14 
15 int cmp(double x)
16 {
17     if (fabs(x)<1e-15) return 0;
18     if (x>0) return 1;
19     return -1;
20 }
21 
22 bool judge(double a, double b, double c, double &x1, double &x2)
23 {
24     double tep = b*b - 4 * a*c;
25     if (cmp(tep)<0) return 0;
26     x1 = (-b + sqrt(tep)) / (2 * a);
27     x2 = (-b - sqrt(tep)) / (2 * a);
28     return 1;
29 }
30 bool judge(circle o, P a, P c)    //线段与圆的关系
31 {
32     double k, b;
33     if (cmp(a.x - c.x) == 0)
34     {//如果为垂直于x轴的线段
35         double t = o.r*o.r - (a.x - o.x)*(a.x - o.x);//半径的平方减去圆心到边的距离的平方
36         if (t<0) return 0;//在圆外
37         double maxy = max(a.y, c.y), miny = min(a.y, c.y), y1 = sqrt(t) + o.y, y2 = o.y - sqrt(t);
38         if (cmp(miny - y1) <= 0 && cmp(y1 - maxy) <= 0) return 1;
39         if (cmp(miny - y2) <= 0 && cmp(y2 - maxy) <= 0) return 1;
40         return 0;
41     }
42     k = (a.y - c.y) / (a.x - c.x);//斜率
43     b = a.y - k*a.x;//截距
44     double x1, x2;
45     int f = judge(k*k + 1, 2 * k*(b - o.y) - 2 * o.x, o.x*o.x + (b - o.y)*(b - o.y) - o.r*o.r, x1, x2);//方程联立得到系数a,b,c,x1,x2
46     if (f == 0) return 0;//b^2-4ac小于0
47     int maxx = max(a.x, c.x), minx = min(a.x, c.x);
48     if (cmp(minx - x1) <= 0 && cmp(x1 - maxx) <= 0) return 1;//交点在线段上
49     if (cmp(minx - x2) <= 0 && cmp(x2 - maxx) <= 0) return 1;
50     return 0;
51 }
52 bool judge(circle o, P a, P b, P c)
53 {
54     if (judge(o, a, b) || judge(o, a, c) || judge(o, b, c)) return 1;
55     return 0;
56 }
57 
58 int main()
59 {
60     int t;
61     circle o;
62     P a, b, c;
63     scanf("%d", &t);
64     while (t--)
65     {
66         scanf("%lf%lf%lf", &o.x, &o.y, &o.r);
67         scanf("%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y);
68         if (judge(o, a, b, c)) puts("Yes");
69         else puts("No");
70     }
71     return 0;
72 }

View Code

 四 、1265 四点共面(计算几何)

  题意:判断给出的6个点是否共面。

  思路:转换判断空间三条直线是还是不是在同一平面,假若方向向量的混合积等于0,则在同一平面。

图片 11图片 12

 1 #include<iostream>
 2 using namespace std;
 3 int nodes[4][3];
 4 int vec[3][3];
 5 int main()
 6 {
 7     int t;
 8     scanf("%d", &t);
 9     while (t--)
10     {
11         for (int i = 0; i < 4; i++)
12         {
13             for (int j = 0; j < 3; j++) scanf("%d", &nodes[i][j]);
14         }
15         for (int i = 1; i < 4; i++)
16         {
17             for (int j = 0; j < 3; j++) vec[i - 1][j] = nodes[i][j] - nodes[i - 1][j];
18         }
19         int v = vec[0][0] * (vec[1][1] * vec[2][2] - vec[2][1] * vec[1][2]) - vec[0][1] * (vec[1][0] * vec[2][2] - vec[2][0] * vec[1][2]) + vec[0][2] * (vec[1][0] * vec[2][1] - vec[2][0] * vec[1][1]);
20         if (v == 0) printf("Yes\n");
21         else printf("No\n");
22     }
23     return 0;
24 }

View Code

 ⑤ 、1264 线段相交(总括几何)

  题意:判断两条线条是还是不是相交。

  思路:看交点是还是不是在两条线段上,注意k不设有的场馆。

图片 13图片 14

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 int main()
 6 {
 7     int t;
 8     int x1, x2, x3, x4, y1, y2, y3, y4;
 9     double k1, k2, b1, b2;
10     scanf("%d", &t);
11     while (t--)
12     {
13         scanf("%d%d%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
14         bool flag = false;
15         if (x1 == x2)
16         {
17             if (x3 != x4)
18             {
19                 k2 = 1.0*(y3 - y4) / (x3 - x4);
20                 b2 = y3 - x3*k2;
21                 double ymd = k2*x1 + b2;
22                 if (x1 >= min(x3, x4) && x1 <= max(x3, x4) && ymd >= min(y1, y2) && ymd <= max(y1, y2)) flag = true;
23             }
24         }
25         else if (x3 == x4)
26         {
27             k1 = 1.0*(y1 - y2) / (x1 - x2);
28             b1 = y1 - x1*k1;
29             double ymd = k1*x3 + b1;
30             if (x3 >= min(x1, x2) && x3 <= max(x1, x2) && ymd >= min(y3, y4) && ymd <= max(y4, y3)) flag = true;
31         }
32         else
33         {
34             k2 = 1.0*(y3 - y4) / (x3 - x4);
35             b2 = y3 - x3*k2;
36             k1 = 1.0*(y1 - y2) / (x1 - x2);
37             b1 = y1 - x1*k1;
38             double xmd = 1.0*(b2 - b1) / (k1 - k2);
39             if (xmd >= min(x1, x2) && xmd <= max(x1, x2) && xmd >= min(x3, x4) && xmd <= max(x3, x4))flag = true;
40         }
41         if (flag)printf("Yes\n");
42         else printf("No\n");
43     }
44 
45     return 0;
46 }

View Code

 陆 、1256 乘法逆元(数论)

  题意:求k,使得k*m=1(mod
n),即k*m%n=1.

  思路:乘法逆元,增添欧几里得。

  注:作用:

12 / 4 mod 7 = ?  结果是3
作者们现在对于数对 (4,7), 能够领略 X = 2是 4 对7的乘法逆元即2*4=1(mod
7)
那么大家有(12 / 4) * (4 * 2 ) = (?) * (1) (mod 7)
除法被全面地倒车为了乘法

图片 15图片 16

 1 #include<iostream>
 2 using namespace std;
 3 //返回d = gcd(a, b);x,y对应于等式ax + by = d中的x、y
 4 long long extendGCD(long long a, long long b, long long &x, long long &y)
 5 {
 6     if (a == 0 && b == 0) return -1;//无最大公约数
 7     if (b == 0)
 8     {
 9         x = 1;
10         y = 0;
11         return a;
12     }
13     long long d = extendGCD(b, a%b, y, x);
14     y -= a / b*x;
15     return d;
16 }
17 //求逆元 ax = 1(mod n)
18 long long modReverse(long long a, long long n)
19 {//要求a,n互质
20     long long x, y;
21     long long d = extendGCD(a, n, x, y);
22     if (d == 1)
23     {
24         return (x%n + n) % n;//防止为负
25     }
26     else return -1;//无逆元
27 }
28 int main()
29 {
30     long long m, n;
31     while (~scanf("%I64d%I64d", &m, &n))
32     {//k*m%n=1=>k*m+x(-n)=1=>k*m=1(mod n)=>m关于模n的乘法逆元为k
33         printf("%I64d\n", modReverse(m, n));
34     }
35 
36     return 0;
37 }

View Code

 7、1240 莫比乌斯函数(数论)

  题意:假若多个数包蕴平方因子,那么miu(n) =
0。例如:miu(4), miu(12), miu(18) = 0。

  即便四个数不包括平方因子,并且有k个区别的质因子,那么miu(n)
= (-1)^k。例如:miu(2), miu(3), miu(30) = -1,miu(1), miu(6), miu(10) =
1。

  给出二个数n, 总计miu(n)。

  思路:①直接求法。算出其因子。

图片 17图片 18

 1 #include <iostream>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 int n;
 7 
 8 int MOD(int a, int b)
 9 {//取余
10     return a - a / b * b;
11 }
12 
13 int miu(int n)
14 {
15     int cnt, k = 0;
16     for (int i = 2; i * i <= n; i++)
17     {
18         if (MOD(n, i))
19         {
20             continue;
21         }
22         cnt = 0;
23         k++;
24         while (MOD(n, i) == 0)
25         {
26             n /= i;
27             cnt++;
28         }
29         if (cnt >= 2)
30         {//存在平方数,值为0
31             return 0;
32         }
33     }
34     if (n != 1)
35     {//大质数
36         k++;
37     }
38     return MOD(k, 2) ? -1 : 1;//奇数个因子,-1;否则1
39 }
40 
41 int main()
42 {
43     while (~scanf("%d",&n))
44     {
45         printf("%d\n",miu(n));
46     }
47     return 0;
48 }

View Code

      ②筛法。

 ⑧ 、1242
斐波那契数列的第N项(矩阵火速幂)

  题意:如题。

  思路:斐波那契数列除了递推式F(n)=F(n-1)+F(n-2),仍是能够用矩阵乘法。

      
图片 19

 

图片 20图片 21

 1 #include <cstdio>    
 2 #include <iostream>    
 3 #include <vector>
 4 #include<cstring>
 5 using namespace std;   
 6 const long long MOD = 1000000009;
 7 long long n;
 8 long long re[2][2];
 9 void mul(long long (*a)[2],long long (*b)[2])  //矩阵乘法    
10 {
11     memset(re, 0, sizeof(re));
12     for(long long i=0;i<2;i++)    
13     {    
14         for(long long k=0;k<2;k++)    
15         {    
16             for(long long j=0;j<2;j++)    
17                 re[i][j] = ( re[i][j] + a[i][k] * b[k][j] ) % MOD;    
18         }    
19     }    
20 }    
21     
22 void solve_pow(long long(*a)[2],long long n) //快速幂    
23 {    
24     long long b[2][2] = {0};
25     for(long long i=0;i<2;i++)
26         b[i][i]=1;   
27     while(n>0)    
28     {    
29         if (n & 1)
30         {
31             mul(b, a);
32             memcpy(b, re, sizeof(re));
33         }
34         mul(a,a);
35         memcpy(a, re, sizeof(re));
36         n >>= 1;    
37     }
38     memcpy(re, b, sizeof(b));
39 }    
40  
41 void solve()    
42 {    
43     long long a[2][2];
44     while(~scanf("%lld",&n) && n!=-1)    
45     {    
46         a[0][0]=1,a[0][1]=1;    
47         a[1][0]=1,a[1][1]=0;    
48         solve_pow(a,n);    
49         printf("%lld\n",re[1][0]);    
50     }    
51 }    
52 int main()    
53 {    
54     solve();    
55     return 0;    
56 }    

View Code

 ⑨ 、1212 无向图最小生成树(图论)

  思路:最小生成树。

  ①Kruskal

图片 22图片 23

 1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 1010;
 6 const int maxe = 50010;
 7 int n, m;
 8 struct edge
 9 {
10     int from;
11     int to;
12     int w;
13     edge(int ff = 0, int tt = 0,int ww=0):from(ff),to(tt),w(ww){ }
14     friend bool operator <(const edge&a, const edge&b)
15     {
16         return a.w > b.w;
17     }
18 };
19 vector<edge>minHeap;
20 int pre[maxn];
21 int Find(int x)
22 {
23     int r = x;
24     while (r != pre[r])
25     {
26         r = pre[r];
27     }
28     int i = x, j;
29     while (i != r)
30     {
31         j = pre[i];
32         pre[i] = r;
33         i = j;
34     }
35     return r;
36 }
37 bool Join(int x,int y)
38 {
39     int fx = Find(x), fy = Find(y);
40     if (fx != fy)
41     {
42         pre[fx] = fy;
43         return false;
44     }
45     return true;
46 }
47 int Kruskal()
48 {
49     for (int i = 0; i <= n; i++) pre[i] = i;
50     int sum = 0;
51     int cnt = 1;
52     while(cnt<n)
53     {
54         pop_heap(minHeap.begin(), minHeap.end());
55         edge tmp = minHeap.back();
56         minHeap.pop_back();
57         if (!Join(tmp.from, tmp.to))
58         {
59             sum += tmp.w;
60             cnt++;
61         }
62     }
63     return sum;
64 }
65 int Solve()
66 {
67     minHeap.clear();
68     for (int i = 1; i <= m; i++)
69     {
70         int u, v, w;
71         scanf("%d%d%d", &u, &v, &w);
72         minHeap.push_back(edge(u, v, w));
73     }
74     make_heap(minHeap.begin(), minHeap.end());
75     return Kruskal();
76 }
77 int main()
78 {
79     while (~scanf("%d%d", &n, &m))
80     {
81         printf("%d\n", Solve());
82     }
83     return 0;
84 }

View Code

  ②Kruskal2

图片 24图片 25

 1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio>
 6 using namespace std;
 7 const int maxn = 1010;
 8 const int maxe = 50010;
 9 int n, m;
10 struct edge
11 {
12     int from;
13     int to;
14     int w;
15     edge(int ff=0,int tt=0,int ww=0):from(ff),to(tt),w(ww){ }
16     friend bool operator<(const edge&a, const edge&b)
17     {
18         return a.w < b.w;
19     }
20 };
21 vector<edge>minheap;
22 bool vis[maxn];
23 int pre[maxn];
24 int Find(int x)
25 {
26     int r = x;
27     while (r != pre[r])
28     {
29         r = pre[r];
30     }
31     int i = x, j;
32     while (i != r)
33     {
34         j = pre[i];
35         pre[i] = r;
36         i = j;
37     }
38     return r;
39 }
40 bool Join(int x, int y)
41 {
42     int fx = Find(x), fy = Find(y);
43     if (fx != fy)
44     {
45         pre[fx] = fy;
46         return false;
47     }
48     return true;
49 }
50 int Kruskal()
51 {
52     for (int i = 0; i <= n; i++) pre[i] = i;
53     sort(minheap.begin(), minheap.end());
54     int cnt = 1;
55     int sum = 0;
56     int i = 0;
57     while (cnt < n)
58     {
59         while (Join(minheap[i].from,minheap[i].to)) i++;
60         sum += minheap[i].w;
61         cnt++;
62     }
63     return sum;
64 }
65 int Solve()
66 {
67     minheap.clear();
68     for (int i = 1; i <= m; i++)
69     {
70         int u, v, w;
71         scanf("%d%d%d", &u, &v, &w);
72         minheap.push_back(edge(u, v, w));
73     }
74     return Kruskal();
75 }
76 int main()
77 {
78     while(~scanf("%d%d", &n, &m))
79     {
80         printf("%d\n", Solve());
81     }
82     return 0;
83 }

View Code

  ②Prime

图片 26图片 27

 1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio>
 6 using namespace std;
 7 const int maxn = 1010;
 8 const int maxe = 50010;
 9 int n, m;
10 struct edge
11 {
12     int to;
13     int w;
14     edge(int tt=0,int ww=0):to(tt),w(ww){ }
15     friend bool operator<(const edge&a, const edge&b)
16     {
17         return a.w > b.w;
18     }
19 };
20 vector<edge>mp[maxn];
21 vector<edge>minheap;
22 bool vis[maxn];
23 int Prime()
24 {
25     memset(vis, 0, sizeof(vis));
26     minheap.clear();
27     vis[1] = true;
28     int sz = mp[1].size();
29     for (int i = 0; i <sz; i++)
30     {
31         minheap.push_back(mp[1][i]);
32     }
33     int cnt = 1;
34     edge tmp;
35     int sum = 0;
36     while (cnt < n)
37     {
38         make_heap(minheap.begin(), minheap.end());
39         do
40         {
41             pop_heap(minheap.begin(), minheap.end());
42             tmp = minheap.back();
43             minheap.pop_back();
44         }while (vis[tmp.to]);
45         sum += tmp.w;
46         vis[tmp.to] = true;
47         cnt++;
48         int u = tmp.to;
49         sz = mp[u].size();
50         for (int i = 0; i < sz; i++)
51         {
52             tmp = mp[u][i];
53             if (!vis[tmp.to])
54             {
55                 minheap.push_back(tmp);
56             }
57         }
58     }
59     return sum;
60 }
61 int Solve()
62 {
63     for (int i = 0; i <= n; i++) mp[i].clear();
64     for (int i = 1; i <= m; i++)
65     {
66         int u, v, w;
67         scanf("%d%d%d", &u, &v, &w);
68         mp[u].push_back(edge(v, w));
69         mp[v].push_back(edge(u, w));
70     }
71     return Prime();
72 }
73 int main()
74 {
75     while(~scanf("%d%d", &n, &m))
76     {
77         printf("%d\n", Solve());
78     }
79     return 0;
80 }

View Code

 十 、1183  编辑距离
字符串相似度算法(编辑距离算法 Levenshtein Distance)

  思路:

  • if i == 0 且 j == 0,edit(i, j) = 0
  • if i == 0 且 j > 0,edit(i, j) = j
  • if i > 0 且j == 0,edit(i, j) = i
  • if i ≥ 1  且 j ≥ 1 ,edit(i, j) == min{ edit(i-1, j) + 1, edit(i,
    j-1) + 1, edit(i-1, j-1) + f(i, j)
    },当第③个字符串的第i个字符不等于第二个字符串的第j个字符时,f(i, j)
    = 1;不然,f(i, j) = 0。

图片 28图片 29

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 1005;
 6 char s1[maxn];
 7 char s2[maxn];
 8 int dp[maxn][maxn];
 9 int main()
10 {
11     while (~scanf("%s%s", s1+1, s2+1))
12     {
13 
14         int ln = strlen(s1+1);
15         int lm = strlen(s2 + 1);
16         for (int i = 0; i <= lm; i++) dp[0][i] = i;
17         for (int i = 0; i <= lm; i++) dp[i][0] = i;
18         for (int i = 1; i <= ln; i++)
19         {
20             for (int j = 1; j <= lm; j++)
21             {
22                 int t = (s1[i] == s2[j] ? 0 : 1);
23                 dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1]+t));
24             }
25         }
26         printf("%d\n", dp[ln][lm]);
27     }
28     return 0;
29 }

View Code

 1一 、1181 质数中的质数(质数筛法)

  题意:求≥n的数的微乎其微的编号也为质数(编号从1发端)的质数。

  思路:线性素数筛。

图片 30图片 31

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 const int maxn = 1000100;
 8 bool isp[maxn];
 9 int prime[maxn], cnt;
10 void makePrime()
11 {
12     memset(isp, true, sizeof(isp));
13     isp[0] = isp[1] = false;
14     cnt = 0;
15     for (int i = 2; i < maxn; ++i)
16     {
17         if (isp[i])//是素数
18         {
19             prime[cnt++] = i;//保存该素数
20         }
21         for (int j = 0; j < cnt && i * prime[j] < maxn; ++j)
22         {
23             isp[i * prime[j]] = false;//当前的数乘以所有已算出的素数都不是素数
24             if (i % prime[j] == 0)//如果i能被某一个最小的素数整除,则退出
25             {
26                 break;
27             }
28         }
29     }
30 }
31 int main()
32 {
33     makePrime();
34     int n;
35     while (~scanf("%d", &n))
36     {
37         int pos = lower_bound(prime, prime + cnt, n) - prime;
38         while (!isp[pos + 1]) pos++;
39         printf("%d\n", prime[pos]);
40     }
41     return 0;
42 }

View Code

 1贰 、中夏族民共和国剩余定理

  题意:1个正整数K,给出K Mod
一些质数的结果,求符合条件的小不点儿的K。

  思路:中夏族民共和国剩余定理。

图片 32图片 33

 1 #include<cstring>
 2 #include<iostream>
 3 #include<cstdio>
 4 #define MAXN 20
 5 #define ll long long
 6 using namespace std;
 7 
 8 ll m[MAXN], p[MAXN];
 9 int n;
10 //a*x=1(mod b)
11 void exgcd(ll a, ll b, ll& x, ll& y)
12 {  //exgcd求乘法取模运算的逆元
13     if (!b)
14     {
15         y = 0, x = 1;
16         return;
17     }
18     else
19     {
20         exgcd(b, a%b, x, y);
21         ll temp = x;
22         x = y;
23         y = temp - a / b*y;
24     }
25 }
26 
27 ll crt()
28 {
29     ll P = 1, ans = 0;
30     for (int i = 0; i<n; i++)
31     {
32         P *= p[i];
33     }
34     for (int i = 0; i<n; i++)
35     {
36         ll mi = P / p[i], x, y;
37         exgcd(mi, p[i], x, y);
38         ans = (ans + m[i] * x*mi) % P;
39     }
40     if (ans<0)
41     {
42         ans += P;
43     }
44     return ans;
45 }
46 
47 int main()
48 {
49     scanf("%d", &n);
50     for (int i = 0; i<n; i++)
51     {
52         scanf("%lld%lld", &p[i], &m[i]);
53     }
54     printf("%lld\n", crt());
55     return 0;
56 }

View Code

 1③ 、1174 区间中最大的数(兰德索罗德MQ)

  题意:求内定区间内的最大值,

  思路:RMQ.

图片 34图片 35

 1 //例如数列3 2 4 5 6 8 1 2 9 7,F[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。 F[1,2]=5,F[1,3]=8,F[2,0]=2,F[2,1]=4……从这里可以看出F[i,0]其实就等于A[i]。这样,DP的状态、初值都已经有了,剩下的就是状态转移方程。
 2 //我们把F[i,j]平均分成两段(因为f[i,j]一定是偶数个数字),从i到i+2^(j-1)-1为一段,i+2^(j-1)到i+2^j-1为一段(长度都为2^(j-1))。
 3 //用上例说明,当i=1,j=3时就是3,2,4,5 和 6,8,1,2这两段。F[i,j]就是这两段的最大值中的最大值。于是我们得到了动态规划方程F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])。
 4 //然后是查询,由于给出的区间不一定是2的次幂,所以需要取一个最小幂覆盖区间。取k=[log2(j-i+1)],向上取整,则有:RMQ(A, i, j)=min{F[i,k],F[j-2^k+1,k]},即将区间分为[i,i+(2^k)-1] [j-(2^k)+1,j],容易证明这两个区间是有重合地方的。
 5 //举例说明,要求区间[2,8]的最大值,就要把它分成[2,5]和[5,8]两个区间,因为这两个区间的最大值我们可以直接由f[2,2]和f[5,2]得到。
 6 #include<iostream>
 7 #include<memory.h>
 8 #include<cstdio>
 9 #include<cmath>
10 #include<algorithm>
11 using namespace std;
12 const int maxn = 10005;
13 int Fmax[maxn][20], Fmin[maxn][20];
14 //[i][j]表示[i,2^j-1]区间内的最值
15 int n, q;
16 void RMQ()
17 {
18     for (int i = 1; i <= n; i++)
19     {
20         int num;
21         scanf("%d", &num);
22         Fmin[i][0] = Fmax[i][0] = num;
23     }
24     for (int j = 1; j < 20; j++)
25     {
26         for (int i = 1; i <= n; i++)
27         {
28             if (i + (1 << j) - 1 <= n)
29             {
30                 Fmax[i][j] = max(Fmax[i][j - 1], Fmax[i + (1 << (j - 1))][j - 1]);
31                 Fmin[i][j] = min(Fmin[i][j - 1], Fmin[i + (1 << (j - 1))][j - 1]);
32             }
33         }
34     }
35 }
36 int main()
37 {
38     while (~scanf("%d", &n))
39     {
40         memset(Fmax, 0, sizeof(Fmax));
41         memset(Fmin, 0, sizeof(Fmin));
42         RMQ();
43         scanf("%d", &q);
44         for (int i = 0; i < q; i++)
45         {
46             int l, r;
47             scanf("%d%d", &l, &r);
48             l++, r++;
49             int k = 0;
50             while ((1 << (k + 1)) <= r - l + 1) k++;
51             //int k = ceil(log(1.0+r - l) / log(2.0));  
52             int maxnum = max(Fmax[l][k], Fmax[r - (1 << k) + 1][k]);
53             int minnum = min(Fmin[l][k], Fmin[r - (1 << k) + 1][k]);
54             printf("%d\n", maxnum);
55         }
56     }
57     return 0;
58 }

View Code

 1④ 、1136 欧拉函数

  题意:对正整数n,欧拉函数是不难或等于n的数中与n互质的数的多寡。

  思路:欧拉函数模板。

  ①直接求法。

图片 36图片 37

 1 //#include<bits/stdc++.h>
 2 #include<iostream>
 3 using namespace std;
 4 //Euler函数表达通式:euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数,x是不为0的整数。euler(1)=1(唯一和1互质的数就是1本身)。 
 5 //欧拉公式的延伸:一个数的所有质因子之和是euler(n)*n / 2。
 6 int euler(int n)
 7 {
 8     int res = n, i;
 9     for (i = 2; i*i <= n; i++)
10     {
11         if (n%i == 0)
12         {
13             res = res / i*(i - 1);
14             while (n%i == 0) n = n / i;
15         }
16     }
17     if (n != 1) res = res / n*(n - 1);
18     return res;
19 }
20 int main()
21 {
22     int n;
23     cin >> n;
24     cout << euler(n) << endl;
25     return 0;
26 }

View Code

  补充:欧拉函数线性筛。

图片 38图片 39

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #define N 40000  
 4 using namespace std;  
 5 int n;  
 6 int phi[N+10],prime[N+10],tot,ans;  
 7 bool mark[N+10];  
 8 void getphi()  
 9 {  
10    int i,j;  
11    phi[1]=1;  
12    for(i=2;i<=N;i++)//相当于分解质因式的逆过程  
13    {  
14        if(!mark[i])  
15            {  
16              prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。  
17              phi[i]=i-1;//当 i 是素数时 phi[i]=i-1  
18              }  
19        for(j=1;j<=tot;j++)  
20        {  
21           if(i*prime[j]>N)  break;  
22           mark[i*prime[j]]=1;//确定i*prime[j]不是素数  
23           if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数  
24           {  
25              phi[i*prime[j]]=phi[i]*prime[j];break;  
26           }  
27           else  phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]],利用了欧拉函数的积性  
28        }  
29    }  
30 }  
31 int main()  
32 {  
33     getphi();  
34 }  

View Code

 1五 、1137 矩阵乘法

  题意:两个n*n的矩阵相乘。

  思路:模拟矩阵乘法。

图片 40图片 41

 1 #include<iostream>
 2 using namespace std;
 3 int a[110][110], b[110][110];
 4 int re[110][110];
 5 int main()
 6 {
 7     int n;
 8     while (~scanf("%d", &n))
 9     {
10         for (int i = 1; i <=n; i++)
11         {
12             for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
13         }
14         for (int i = 1; i <= n; i++)
15         {
16             for (int j = 1; j <= n; j++) scanf("%d", &b[i][j]);
17         }
18         for (int i = 1; i <= n; i++)
19         {
20             for (int j = 1; j <= n; j++)
21             {
22                 re[i][j] = 0;
23                 for (int k = 1; k <= n; k++)
24                 {
25                     re[i][j] += a[i][k] * b[k][j];
26                 }
27             }
28         }
29         for (int i = 1; i <= n; i++)
30         {
31             for (int j = 1; j <= n; j++)
32             {
33                 if (j > 1) printf(" ");
34                 printf("%d", re[i][j]);
35             }
36             printf("\n");
37         }
38     }
39     return 0;
40 }

View Code

 16、1135 原根

  题意:设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的3个原根。(在那之中φ(m)表示m的欧拉函数)给出一个质数P,找出P最小的原根。

  思路:1.原根定义:设m>1,gcd(a,m)=1,使得a^r≡1(mod
m)创造的细微的r,称为a对模m的阶。
  2.定律:若是模m有原根,那么她一共有φ(φ(m))个原根。
  3.定律:如若p为素数,那么素数p一定期存款在原根,并且模p的原根的个数为φ(p-1)个。
  4.定律:若是m是正整数,a是整数,假使a模m的阶等于φ(m),则称a为模m的1个原根。
  5.模m有原根的充要条件:m=2,4,P^a,2*P^a……
  求模素数P的原根的不二法门:对P-1素因子分解,即P-1=(P1^a1)(P2^a2)…..(Pk^ak)。,若恒有g^((P-1)/Pi)≠1(mod
P)创建,那么g就是P的原根(对于合数而言,只要求把P-1换到φ(P)即可)

图片 42图片 43

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 typedef long long  LL;
 8 const int maxn = 1e6 + 10;
 9 int prime[maxn];//存储素数
10 int sprime[maxn];//存储P-1的素因子
11 bool isp[maxn];//结果只有0和1,判断是否为素数
12 int k;//记录Maxn以内的素数个数
13 int cnt;//记录素因子的个数
14 void is_prime()
15 {
16     memset(isp,true,sizeof(isp));//将所有的二进制数都标为1
17     for (int i = 2; i<maxn; i++)
18     {
19         if (isp[i])
20         {
21             prime[k++] = i;
22             for (int j = i + i; j<maxn; j += i)
23                 isp[j] = false;
24         }
25     }
26 }
27 void Divide(int n)//将n分解为素因子
28 {
29     cnt = 0;
30     int t = (int)sqrt(1.0*n);
31     for (int i = 0; prime[i] <= t; i++)
32     {
33         if (n%prime[i] == 0)
34         {
35             sprime[cnt++] = prime[i];
36             while (n%prime[i] == 0)//因为有可能有多个peime[i]
37                 n /= prime[i];
38         }
39     }
40     if (n>1)
41         sprime[cnt++] = n;//可能只有自己一个素因子
42 }
43 //求a^b%mod
44 LL modexp(LL a, LL b, int mod)//快速幂取模
45 {
46     LL res = 1;
47     while (b>0)
48     {
49         a = a%mod;
50         if (b & 1)
51             res = res*a%mod;
52         b = b >> 1;
53         a = a*a%mod;
54     }
55     return res;
56 }
57 
58 int main()
59 {
60     int p;
61     is_prime();
62     while (~scanf("%d", &p))
63     {
64         Divide(p - 1);
65         for (int g = 2; g<p; g++)
66         {
67             int flag = 1;
68             for (int i = 0; i<cnt; i++)
69             {
70                 int t = (p - 1) / sprime[i];
71                 if (modexp(g, t, p) == 1)
72                 {
73                     flag = 0;
74                     break;
75                 }
76             }
77             if (flag)
78             {
79                 int root = g;
80                 printf("%d\n", root);
81                 break;//去掉break的话是求所有的原根,加上break是求最小的原根、
82             }
83         }
84     }
85     return 0;
86 }

View Code

 1柒 、1072 威佐夫游戏

  题意:有2堆石子。A
B多人轮番拿,A先拿。每一遍能够从一堆中取自由个或从2堆中取相同数量的石子,但不可不取。获得结尾1颗石子的人克服。假设A
B都十分明白,拿石子的长河中不会冒出失误。给出2堆石子的数码,问最终什么人能收获竞赛。 例如:2堆石子分别为3颗和5颗。那么不论A如何拿,B都有相应的格局获得最终1颗。 

  思路:http://blog.csdn.net/leibniz\_zhang/article/details/52221542

     http://blog.csdn.net/theprinceofelf/article/details/7225206

     http://blog.csdn.net/h1021456873/article/details/49748659

图片 44图片 45

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int spc[4002000];
 6 bool vis[4002000];
 7 int main()
 8 {
 9     int k = 1;
10     memset(spc, 0, sizeof(spc));
11     memset(vis, true, sizeof(vis));
12     for (int i = 1; i <= 2000000; i++)
13     {//当一个人面对局势(0,0),(1,2),(3,5),(4,7),(6,10)...必败,而非此规律的局势可以通过一步便达到这种局势
14         //特点:(x,y)x为前面未出现的最小值;该局势为第(y-x+1)个
15         if (vis[i])
16         {
17             spc[i] = i + k;
18             vis[spc[i]] = false;
19             k++;
20         }
21     }
22     int t;
23     scanf("%d", &t);
24     int a, b;
25     while (t--)
26     {
27         scanf("%d%d", &a, &b);
28         if (a>b)
29             swap(a, b);
30         if (spc[a] == b)
31             printf("B\n");
32         else
33             printf("A\n");
34     }
35     return 0;
36 }

View Code

1捌 、1185 威佐夫游戏 V2

  题意:同上一题。

  思路:由于数一点都不小,不再递推求,直接用黄金分割求,做乘法模拟。

图片 46图片 47

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define LL long long
 7 LL a, b, c, qian, hou, pp, mod = 1000000000;
 8 LL gold[3] = { 618033988,749894848,204586834 }; //将 0.618033988749894848204586834... 拆成整数放进数组里
 9 //ak =[k(1+√5)/2],bk= ak + k (k=0,1,2,...n 方括号表示取整函数)
10 int main()
11 {
12     int t; scanf("%d", &t);
13     while (t--)
14     {
15         scanf("%lld%lld", &a, &b);
16         if (a>b)
17             swap(a, b);
18         c = b - a;
19         qian = c / mod; hou = c%mod; //把10 ^ 18分成两部分10 ^ 9
20         LL lll = hou*gold[2];//乘法模拟
21         lll = qian*gold[2] + hou*gold[1] + lll / mod;
22         lll = qian*gold[1] + hou*gold[0] + lll / mod;
23         lll = c + qian*gold[0] + lll / mod;
24         if (a == lll)
25             printf("B\n");
26         else
27             printf("A\n");
28     }
29     return 0;
30 }

View Code

 

 

 

相关文章