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之外的最小公因数
然后我就不会了
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了好多次
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);
}
转化成整数也行
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\)是二的倍数就行了
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(地板)==下取整
|
5.7651 自来水供给
有n个村子,坐落在从县城出发的一条公路上。
现在要通过安装水管,从县城向各村供给自来水。水管有粗细两种,粗管可供给任意数量的村子,而细管只能供给一个村子。粗管每公里8000元,细管每公里2000元。
问如何搭配粗管和细管,使得费用最低?
输入:县城的距离从近到远给出各村与上一个的距离
如图(好像不太清,算了,忽略)
因为8000/2000=4,所以后4个连细管,前面连粗管
然而好像必须有一条粗管(题解写的,不要问我为啥),又WA了 /(ㄒoㄒ)/~~
|
6.7652 乘积最大的拆分
将正整数n拆分为若干个互不相等的自然数之和,问如何拆分可以使得它们的乘积最大?从小到大输出。
∵ 若1作因数,则显然乘积不会最大.
∴ 把n分拆成若干个互不相等的自然数的和,因数个数越多,乘积越大.为了使因数个数尽可能地多,我们把n分成2+3…+x直到和大于等于n.
1.若和比n大1,则因数个数至少减少1个,为了使乘积最大,应去掉最小的2,并将最后一个数(最大)加上1.
2.若和比n大k(k≠1),则去掉等于k的那个数,便可使乘积最大.
|
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)\)
|
8.7654 等差数列末项计算
给出一个等差数列的前两项a1,a2,求第n项是多少。
这个还用说么,O__O"… 不愧是小学数学
|
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](看起来可以用前缀和)
|
10.7656 李白的酒
李白街上走,提壶去打酒。遇店加一倍,见花喝一斗。n遇店和花,喝光壶中酒。试问壶中原有多少酒?
释义:李白提壶上街买酒、喝酒,每次遇到酒店,便将壶中的酒量增添一倍,而每次见到花,便喝酒一斗,这样他遇店、见花经过n次,正好把酒全喝完了。问:壶中原有多少酒。(n<=100,舍入到小数点后五位)
O(n)的暴力
\((((x\times 2-1)\times 2-1)\times 2-1)\times 2-1...=0\)
|
11.7657 连乘积末尾0的个数
给定两个正整数a,b(a < b <= 10000)。求连乘积:
a×(a+1)×(a+2)×...×(b-1)×b 的末尾有多少个0?
求从a~b中,每个数的质因数中有几个2,几个5
其中小的那个数就是结果
|
12.7826 分苹果
把一堆苹果分给n个小朋友,要使每个人都能拿到苹果,而且每个人拿到的苹果数都不同的话,这堆苹果至少应该有多少个?
1个,2个,3个。。。。。。
|
13.7827 质数的和与积
两个质数的和是S,它们的积最大是多少?
尽量往中间靠,积最大,枚举判断是不是质数就好了
|
14.7828 最大公约数与最小公倍数
两个正整数的最大公约数是G,最小公倍数是L,它们的和最小是多少?
∵gcd(x,G*L/x)=G ①
∴gcd(x/G,L/x)=1
即gcd(x,L/G/x)=1 ②
直接用①写应该也可以,②的复杂度应该会低一点
|
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)\)
|
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......
|
17.7831 计算星期几
假设今天是星期日,那么过a^b天之后是星期几?
暴力。。。
|
18.7832 最接近的分数
分母不超过 N 且 小于 A/B 的最大最简分数是多少?
x/y < A/B
可以求出对于每个y,最大的x,直接求x/y,取最小
|
19.7833 幂的末尾
幂a^b的末3位数是多少?
mod 1000 算呗
|
20.7834 分成互质组
给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?
我确实不知道我写的是个啥。。。
|