Author Archives: boleyn.su

这是2009年清华大学自主招生数学试题（理科）。 思考时间，答案在下面（字体是白色的）。 答案是3 11 19。 首先它是一个解，下面我们证明没有其它解。 设最小的一个数为X，那么数列为X,X+8,X+16。 然后 X mod 3 = X mod 3 X + 8 mod 3 = X+ 2 mod 3 X + 16 mod 3 =X + 1 mod 3 所以无论X为何值，这个数列中都有一个数是3的倍数，又它们都是质数，所以只可能是有一个数是3，那么显然这个问题解决了。

NOIP2010即将到来，这道题用来练练手感。 这道题的思路就是分解质因数。 首先，不难得到gcd(x/a1,a0/a1)=1以及gcd(b1/x,b1/b0)=1。 假设对于一个质因数y，a0含有a0c个y，a1含有a1c个y，b0含有b0c个y，b1含有b1c个y。 那么不难得到，如果a0c<a1c，那么就无解；如果a0c=a1c，那么x至少含有a1c个y；如果a0c>a1c，那么x只可能含有a1c个y。 同理，如果b1c<b0c，那么就无解；如果b1c=b0c，那么x至多含有b1c个y；如果b1c>b0c，那么x只可能含有b1c个y。 由此，可以求出对于每一个质数，x可能含有几个它，并求出一共有多少种选择方式。然后根据乘法原理，将每一个质数的选择方案数乘起来，就得到了答案。 CODE: /* AUTHOR: Su Jiao DATE: 2010-10-14 DESCRIPTION: $DESCRIPTION */ #include <stdio.h>   const int MAXSIZE=5000; int prime_table[MAXSIZE]; int prime_table_size; void initialize_prime_table() {     prime_table_size=0;     prime_table[prime_table_size++]=2;     for (int i=3;prime_table_size<MAXSIZE;i++)     {         bool is_prime=true;         for (int j=0;j<prime_table_size;j++)             if (i%prime_table[j]==0)             {                is_prime=false;              […]

先离线处理出在[0,10^9)内中所有平方末尾数为987654321的数，然后显然应该写成下面那样。 CODE: /* AUTHOR: Su Jiao DATE: 2010-9-11 DESCRIPTION: $DESCRIPTION */ #include <stdio.h>   int main() {     /*     for (long long int i=0;i<1000000000;i++)         if (i*i%1000000000==987654321) printf(“%d\n”,int(i));     output:     111111111     119357639     380642361     388888889     611111111     619357639     880642361     888888889     */     int n;     scanf(“%d”,&n);     […]

数学题。扩展欧几里得解模同余方程。 CODE: /* AUTHOR: Su Jiao DATE: 2010-8-26 DESCRIPTION: $DESCRIPTION */ #include <iostream> #include <math.h> using namespace std;   #define lli long long int #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define ceil_div(a,b) ceil(double(a)/double(b)) #define floor_div(a,b) floor(double(a)/double(b))   lli gcd(lli a,lli b,lli& x,lli& y) {     //ax+by=gcd(a,b)     if (b==0)     {        x=1,y=0;        return […]

数学题。一个数能被3整除，当且仅当它的各位数的和能被3整除。 CODE: /* AUTHOR: Su Jiao DATE: 2010-8-26 DESCRIPTION: $DESCRIPTION */ #include <stdio.h> int main() {     int N;     scanf(“%d”,&N);     printf(“%d\n”,N/3*2+(N%3==2)); }  

动态规划经典题目，据说是IOI上出现的首个动态规划题目。 CODE: /* AUTHOR: Su Jiao DATE: 2010-8-24 DESCRIPTION: $DESCRIPTION */ #include <iostream> using namespace std;   const int MAXF=100+2,MAXV=100+2; const int oo=19930309; int F,V; int A[MAXF][MAXV]; int f[MAXF][MAXV];   void print(int v,int i) {      if (i)      {         int j;         for (j=1;j<=V;j++)             if (f[i][j]==v)                break;         print(v-A[i][j],i-1);         cout<<j<<char(i==F?’\n’:’ […]

最短路。 CODE: /* AUTHOR: Su Jiao DATE: 2010-8-24 DESCRIPTION: $DESCRIPTION */ #include <iostream> using namespace std;   const int MAXE=14000*2; const int MAXV=300+2; typedef struct struct_edge* edge; struct struct_edge{int v,d;edge n;}; struct node {        int c,r,t[2];        int color(int timeline)        {            int alpha=timeline%(t[0]+t[1]);            if (r<=alpha&&alpha<r+t[!c]) return !c;            else return c; […]

求最大公约数。 CODE: /* AUTHOR: Su Jiao DATE: 2010-8-24 DESCRIPTION: $DESCRIPTION */ #include <iostream> using namespace std;   int main() {     int N,answer=0;     cin>>N;     for (int i=1;i<=N;i++)     {         int a=N,b=i,t;         while (b) t=a,a=b,b=t%b;         if (a==1) answer++;     }     cout<<answer<<endl; }  

欧拉路。 CODE: /* AUTHOR: Su Jiao DATE: 2010-8-24 DESCRIPTION: $DESCRIPTION */ #include <iostream> using namespace std;   const int MAXE=100*2; const int MAXV=6–0+1; typedef struct struct_edge* edge; struct struct_edge{int v,id;char dir;edge n;}; struct_edge pool[MAXE]; edge top=pool; edge adj[MAXV]; int degree[MAXV]; int used[MAXE/2]; int list[MAXE/2+1]; int listtop; int size[MAXV][MAXV]; edge edges[MAXV][MAXV][MAXE]; int printed[MAXE/2]; void add_edge(int u,int […]

经典题目。 CODE: /* AUTHOR: Su Jiao DATE: 2010-8-24 DESCRIPTION: $DESCRIPTION */ #include <iostream>   int main() {     int a,b;     std::cin>>a>>b;     std::cout<<a+b<<std::endl; }