这是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,那么显然这个问题解决了。
Author Archives: boleyn.su
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 […]
SGU100[A+B]
经典题目。 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; }