请写出所有三个数均为质数,且公差为8的等差数列,并证明你的结论

这是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,那么显然这个问题解决了。

NOIP2009[Hankson的趣味题/son]

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;              […]

SGU107[987654321 problem]

先离线处理出在[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);     […]

SGU106[The equation]

数学题。扩展欧几里得解模同余方程。 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 […]

SGU105[Div 3]

数学题。一个数能被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)); }  

SGU104[Little shop of flowers]

动态规划经典题目,据说是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’:’ […]

SGU103[Traffic Lights]

最短路。 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; […]

SGU102[Coprimes]

求最大公约数。 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; }  

SGU101[Domino]

欧拉路。 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 […]