openjudge小学奥数

10月 8, 2015

1.7647 余数相同问题

已知三个正整数 a，b，c ( <=1000000 )。
现有一个大于1的整数x，将其作为除数分别除a，b，c，得到的余数相同。
请问满足上述条件的x的最小值是多少？
数据保证x有解。

不小心写了个暴力
本来是这样想的：
∵ a ≡ b ≡ c ( mod x )
∴ ( a - b ) % x = ( a - c ) % x = 0
∴ x = ( a - b ) 和 ( a - c ) 除1之外的最小公因数
然后我就不会了

#include<cstdio>
using namespace std;
int a,b,c;
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	for(int i=2;;i++)
	  if(a%i==b%i&&a%i==c%i)
	    {printf("%d",i);return 0;}
    /*貌似还是个暴力
    x=a-b;y=a-c;
	for(int i=2;;i++)
	  if(!(x%i)&&!(y%i))
	  {printf("%d",i);return 0;}*/
}

2.7648 蓄水池水管问题

蓄水池有甲、丙两条进水管和乙、丁两条排水管。
要灌满一池水，单开甲管需要a小时，单开丙管需要c小时；要排光一池水，单开乙管需要b小时，单开丁管需要d小时。( a < b , c < d ，且a,b,c,d <= 10)
现在池内没有水，如果按甲乙丙丁的顺序循环单开各水管，每次每管开1小时，则多长时间后水开始溢出水池？(舍入到小数点后两位。)
保证一定会在有限时间内出现水溢出水池的情况。

才开始忘了考虑a==1的情况，WA了好多次

#include<cstdio>
using namespace std;
int a,b,c,d;
double tot,ans;
int main()
{
	scanf("%d%d%d%d",&a,&b,&c,&d);
        if(a==1) ans=1.00;
        else 
	for(int t=1;;t++)
	{
		if(t%2)
		{
			tot+=1.0/a-1.0/b;
			if(tot+1.0/c>0.99999)
			  {ans=t*2.0+(1.0-tot)*c;break;}
		}
		else 
		{
			tot+=1.0/c-1.0/d;
		    if(tot+1.0/a>0.99999)
		      {ans=t*2.0+(1.0-tot)*a;break;}
		}
	}
	printf("%.2lf",ans);
}

转化成整数也行

#include<cstdio>
using namespace std;
int a,b,c,d,x,tot;
double ans;
int main()
{
	scanf("%d%d%d%d",&a,&b,&c,&d);
	tot=a*b*c*d;
	for(int t=1;;t++)
	{
		if(t%4==1)
		{
			x+=tot/a;
			if(x>=tot)
			{printf("%.2f",t+a-1.0*a*x/tot);return 0;}
		}
		else if(t%4==2) x-=tot/b;
		else if(t%4==3)
		{
			x+=tot/c;
		    if(x>=tot)
		    {printf("%.2f",t+c-1.0*c*x/tot);return 0;}
		}
		else x-=tot/d;
	}
}

3.7649 我家的门牌号

我家住在一条短胡同里，这条胡同的门牌号从1开始顺序编号。
若其余各家的门牌号之和减去我家门牌号，恰好等于n（<100000)，求我家的门牌号及总共有多少家。
数据保证有唯一解。

设我家x，一共y，则\(y\times (y+1)/2-2\times x=n\)
所以\(y\times (y+1)/2-n\)是二的倍数就行了

#include<cstdio>
using namespace std;
int x,y,n;
int main()
{
	scanf("%d",&n);
	for(y=1;;y++)
	{
		x=y*(y+1)/2-n;
		if(x>0&&!(x%2))
		{
			x/=2;
			if(x<=y) break;
		}
	}
	printf("%d %d",x,y);
}

4.7650 不定方程求解

给定正整数a，b，c。求不定方程 ax+by=c 关于未知数x和y的所有非负整数解组数。

明显的exgcd嘛，当然暴力也能过 exged:
函数求出\(ax+by=gcd(a,b)\)的其中一组解
\(ax+by=c\)的解就是\(x\times c/d,y\times c/d\)（当然如果\(d\nmid c\)的话，无整数解）
∴\(p\times a+q\times b=c\)的其他整数解满足：
\(xx = x+b/d\times t\)
\(yy = y-a/d\times t (t∈Z)\)
∵求非负整数解
∴\(-x\times d/b<=t<=d\times y/a\)
∴\(ans=floor(1.0\times d\times y/a)-ceil((-1.0)\times x\times d/b)+1\)
ps: ceil(天花板)==上取整，floor(地板)==下取整

#include<cstdio>
#include<cmath>
using namespace std;
int x,y,ans,d,a,b,c;
int exgcd(int a,int b,int &d,int &x,int &y)
{
    if(!b) { d=a; x=1; y=0; }
   else { exgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	exgcd(a,b,d,x,y);
	if(!(c%d))
	{
		x=x*c/d;y=y*c/d;
		ans=floor(1.0*d*y/a)-ceil((-1.0)*x*d/b)+1;
	}
	printf("%d",ans);
}

5.7651 自来水供给

有n个村子，坐落在从县城出发的一条公路上。
现在要通过安装水管，从县城向各村供给自来水。水管有粗细两种，粗管可供给任意数量的村子，而细管只能供给一个村子。粗管每公里8000元，细管每公里2000元。
问如何搭配粗管和细管，使得费用最低？
输入：县城的距离从近到远给出各村与上一个的距离

如图（好像不太清，算了，忽略）
因为8000/2000=4，所以后4个连细管，前面连粗管
然而好像必须有一条粗管（题解写的，不要问我为啥），又WA了 /(ㄒoㄒ)/~~

#include<iostream>
#include<cstdio>
using namespace std;
int n,ans,a[101],sum[101];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
	for(int i=max(2,n-3);i<=n;i++) ans+=a[i]*2000*(n-i+1);
	ans+=sum[max(1,n-4)]*8000;
	printf("%d",ans);
}

6.7652 乘积最大的拆分

将正整数n拆分为若干个互不相等的自然数之和，问如何拆分可以使得它们的乘积最大？从小到大输出。

∵ 若1作因数,则显然乘积不会最大.
∴ 把n分拆成若干个互不相等的自然数的和,因数个数越多,乘积越大.为了使因数个数尽可能地多,我们把n分成2+3…+x直到和大于等于n.
1.若和比n大1,则因数个数至少减少1个,为了使乘积最大,应去掉最小的2,并将最后一个数（最大）加上1.
2.若和比n大k（k≠1）,则去掉等于k的那个数,便可使乘积最大.

#include<cstdio>
#include<cmath>
using namespace std;
int n,x,delta;
int main()
{
	scanf("%d",&n);
	if(n==1) {printf("1");return 0;}
	x=sqrt(2*n+2.25)+0.5;//求根公式
	delta=(x-1)*(x+2)/2-n;
	if(delta<2)
	{
	    for(int i=delta+2;i<x;i++)  printf("%d ",i);
	    printf("%d ",x+1);
	}
	else
	{
	    for(int i=2;i<=x;i++)
	      if(i!=delta)  printf("%d ",i);	
	}
}

7.7653 地球人口承载力估计

假设地球上的新生资源按恒定速度增长。照此测算，地球上现有资源加上新生资源可供x亿人生活a年，或供y亿人生活b年。( x > y，a < b，ax < by )
为了能够实现可持续发展，避免资源枯竭，地球最多能够养活多少亿人？(舍入到小数点后两位)

设现有资源为z，再生速度为v（即一年所生资源可养活v亿人），则为避免资源枯竭，最多养活v亿人。
\(z + v \times a = x \times a\) ①
\(z + v \times b = y \times b\) ②
由①-②，得\(v\times (a-b)=x\times a-y\times b\)，即\(v=(x\times a-y\times b)/(a-b)\)

#include<cstdio>
using namespace std;
int x,a,y,b;
int main()
{
	scanf("%d%d%d%d",&x,&a,&y,&b);
	printf("%.2f",1.0*(x*a-y*b)/(a-b));
}

8.7654 等差数列末项计算

给出一个等差数列的前两项a1，a2，求第n项是多少。

这个还用说么，O__O"… 不愧是小学数学

#include<cstdio>
using namespace std;
int a1,a2,n;
int main()
{
	scanf("%d%d%d",&a1,&a2,&n);
	printf("%d",a1+(n-1)*(a2-a1));
}

9.7655 回文数个数

不超过n位的正整数中，有多少个回文数？(n<=10)

一位数：1,2,3,...,9
两位数：11,22,33,...,99
三位数：101,111,...191,201,...999
四位数：1001,1111,...,1991,2001,...,9999
......
所以对于n位数
第1位有9种选法（不能是0），第2~(n+1)/2位各有10种
所以对于第n位，ans=\(9\times 10^{(n-1)/2}\)
所以不超过n的数中的回文数就是ans[1]+...+ans[n]（看起来可以用前缀和）

#include<cstdio>
using namespace std;
int n,ans,a[11]={0,9,9,90,90,900,900,9000,9000,90000,90000};
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  ans+=a[i];
	printf("%d",ans);
}

10.7656 李白的酒

李白街上走，提壶去打酒。遇店加一倍，见花喝一斗。n遇店和花，喝光壶中酒。试问壶中原有多少酒？
释义：李白提壶上街买酒、喝酒，每次遇到酒店，便将壶中的酒量增添一倍，而每次见到花，便喝酒一斗，这样他遇店、见花经过n次，正好把酒全喝完了。问：壶中原有多少酒。(n<=100,舍入到小数点后五位)

O(n)的暴力
\((((x\times 2-1)\times 2-1)\times 2-1)\times 2-1...=0\)

#include<cstdio>
using namespace std;
int n;
float ans;
int main()
{
	scanf("%d",&n);
	while(n--)
	  ans=(ans+1)/2.0;
	printf("%.5f",ans);
}

11.7657 连乘积末尾0的个数

给定两个正整数a，b（a < b <= 10000）。求连乘积：
a×(a+1)×(a+2)×...×(b-1)×b 的末尾有多少个0？

求从a~b中，每个数的质因数中有几个2，几个5
其中小的那个数就是结果

#include<iostream>
#include<cstdio>
using namespace std;
int x,y,a,b;
int main()
{
	scanf("%d%d",&x,&y);
	for(int ii=x;ii<=y;ii++)
	{
		int i=ii;
		while(!(i%2)) i/=2,a++;
		while(!(i%5)) i/=5,b++;
	}
	printf("%d",min(a,b));
}

12.7826 分苹果

把一堆苹果分给n个小朋友，要使每个人都能拿到苹果，而且每个人拿到的苹果数都不同的话，这堆苹果至少应该有多少个？

1个，2个，3个。。。。。。

#include<cstdio>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	printf("%d",n*(n+1)/2);
}

13.7827 质数的和与积

两个质数的和是S，它们的积最大是多少？

尽量往中间靠，积最大，枚举判断是不是质数就好了

#include<cstdio>
using namespace std;
int n;
bool yes(int x)
{
	for(int i=2;i<=x;i++)
	{
		if(i*i>x) return 1;
		if(!(x%i)) return 0;
	}
}
int main()
{
	scanf("%d",&n);
	for(int x=n/2;x>1;x--)
	{
		int y=n-x;
		if(yes(x)&&yes(y))  
		{
			printf("%d",x*y);return 0;
		}
	}
}

14.7828 最大公约数与最小公倍数

两个正整数的最大公约数是G，最小公倍数是L，它们的和最小是多少？

∵gcd(x,G*L/x)=G ①
∴gcd(x/G,L/x)=1
即gcd(x,L/G/x)=1 ②
直接用①写应该也可以，②的复杂度应该会低一点

#include<cstdio>
using namespace std;
int G,L,cheng,ans=20000;
int gcd(int a,int b)
{
    while(b)
    {
        int r=b;
        b=a%b;
        a=r;
    }
    return a;
}
int main()
{
	scanf("%d%d",&G,&L);
	cheng=L/G;
	for(int x=sqtr(cheng);x;x--)
	{
		if(cheng%x) continue;
		int y=cheng/x;
		int g=gcd(x,y);
		if(g==1)
		  {printf("%d",(x+y)*G);reutnr 0;}
	}	
}

15.7829 神奇序列求和

有一个序列，初始时只有两个数x和y，之后每次操作时，在原序列的任意两个相邻数之间插入这两个数的和，得到新序列。举例说明：
初始：1 2
操作1次：1 3 2
操作2次：1 4 3 5 2
......
问操作n次之后，得到的序列的所有数之和是多少？

n<=10 可以直接暴力。。。
认真的求：
初始:和为x+y
1:和为2(x+y)
2:和为5(x+y)
3:和为14(x+y)
4:和为41(x+y)
......
∴ \(An = An-1 \times 3 - 1\)
即 \(An - 1/2 = 3 \times ( A_{n-1} - 1/2 )\)
∴ \(An = 3/2 \times 3^{n-1} + 1/2 = ( 3^n + 1 ) / 2\)
∴ \(ans = An \times (x+y)\)

#include<cstdio>
using namespace std;
int x,y,n,power[]={1,3,9,27,81,243,729,2187,6561,19683,59049};
int main()
{
	scanf("%d%d%d",&x,&y,&n);
	printf("%d",(power[n]+1)/2*(x+y));
}

16.7830 求小数的某一位

分数a/b化为小数后，小数点后第n位的数字是多少？

手推的
拿20/7举例子：
- 20/7 = 2 + 6/7
- 60/7 = 8 + 4/7
- 40/7 = 5 + 5/7
- 50/7 = 7 + 1/7
- 10/7 = 1 + 3/7
- ..........

所以20/7=2.8571......

#include<cstdio>
using namespace std;
int n,a,b,x;
int main()
{
	scanf("%d%d%d",&a,&b,&n);
	for(int i=1;i<=n;i++)
	{
		x=a/b;
		a=(a-x*b)*10;
	}
	printf("%d",a/b);
}

17.7831 计算星期几

假设今天是星期日，那么过a^b天之后是星期几？

暴力。。。

#include<cstdio>
using namespace std;
int ans=1,a,b;
int main()
{
	scanf("%d%d",&a,&b);
	a%=7;
	for(int i=1;i<=b;i++)  ans=(ans*a)%7;
	if(ans==0) printf("Sunday");
	else if(ans==1) printf("Monday");
	else if(ans==2) printf("Tuesday");
	else if(ans==3) printf("Wednesday");
	else if(ans==4) printf("Thursday");
	else if(ans==5) printf("Friday");
	else if(ans==6) printf("Saturday");
}

18.7832 最接近的分数

分母不超过 N 且小于 A/B 的最大最简分数是多少？

x/y < A/B
可以求出对于每个y，最大的x，直接求x/y，取最小

#include<cstdio>
using namespace std;
int n,a,b,ansx,ansy;
double minn=1000;
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	for(int y=1;y<=n;y++)
	{
		int x=a*y/b;
		if(b*x>=a*y) x--;
		if(1.0*a/b-1.0*x/y<minn)
		  ansx=x,ansy=y,minn=1.0*a/b-1.0*x/y;
	}
	printf("%d %d",ansx,ansy);
}

19.7833 幂的末尾

幂a^b的末3位数是多少？

mod 1000 算呗

#include<cstdio>
using namespace std;
int ans=1,a,b;
int main()
{
	scanf("%d%d",&a,&b);
	for(int i=1;i<=b;i++)
		ans=(a*ans)%1000;
	printf("%03d",ans);
}

20.7834 分成互质组

给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

我确实不知道我写的是个啥。。。

#include<cstdio>
using namespace std;
int minn=11,n,tot,g[11][11],a[11];
bool no[11];
int gcd(int a,int b)
{
    while(b)
      {
      	int r=b;b=a%b;a=r;
      }
    return a;
}
void search(int num,int tot)
{
	if(num>n)
	{
		if(tot<minn) minn=tot;
		return;
	}
	int no[11]={0},yes=0;
	for(int i=1;i<=tot;i++)
	  for(int j=1;j<=g[i][0];j++)
	    if(gcd(g[i][j],a[num])!=1) 
	    {	no[i]=1;break;    }
	for(int i=1;i<=tot;i++)
	  if(!no[i])
	  {
	  	yes=1;
	  	g[i][++g[i][0]]=a[num];
	  	search(num+1,tot);
	  	g[i][g[i][0]--]=0;
	  }
	if(!yes) 
	{
		g[++tot][0]=1;g[tot][1]=a[num];
		search(num+1,tot);
		g[tot][1]=g[tot][0]=0;tot--;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	g[1][0]=1;g[1][1]=a[1];
	search(2,1);
	printf("%d",minn);
}

数学