这个好像最简单了吧，10行就能A
已知三个正整数 a，b，c ( <=1000000 )。
不小心写了个暴力1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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;}*/
}
蓄水池有甲、丙两条进水管和乙、丁两条排水管。
才开始忘了考虑a==1的情况，WA了好多次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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);
}
转化成整数也行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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;
}
}
我家住在一条短胡同里，这条胡同的门牌号从1开始顺序编号。
设我家x，一共y，则y × ( y + 1 ) / 2 − 2 × x = n y\times (y+1)/2-2\times x=n y × ( y + 1 ) / 2 − 2 × x = n y × ( y + 1 ) / 2 − n y\times (y+1)/2-n y × ( y + 1 ) / 2 − n 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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);
}
给定正整数a，b，c。求不定方程 ax+by=c 关于未知数x和y的所有非负整数解组数。
明显的exgcd嘛，当然暴力也能过
exged: a x + b y = g c d ( a , b ) ax+by=gcd(a,b) a x + b y = g c d ( a , b ) a x + b y = c ax+by=c a x + b y = c x × c / d , y × c / d x\times c/d,y\times c/d x × c / d , y × c / d d ∤ c d\nmid c d ∤ c p × a + q × b = c p\times a+q\times b=c p × a + q × b = c x x = x + b / d × t xx = x+b/d\times t x x = x + b / d × t
− x × d / b < = t < = d × y / a -x\times d/b<=t<=d\times y/a − x × d / b < = t < = d × y / a a n s = f l o o r ( 1 . 0 × d × y / a ) − c e i l ( ( − 1 . 0 ) × x × d / b ) + 1 ans=floor(1.0\times d\times y/a)-ceil((-1.0)\times x\times d/b)+1 a n s = f l o o r ( 1 . 0 × d × y / a ) − c e i l ( ( − 1 . 0 ) × x × d / b ) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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);
}
有n个村子，坐落在从县城出发的一条公路上。
如图（好像不太清，算了，忽略）
1
2
3
4
5
6
7
8
9
10
11
12
13
#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);
}
将正整数n拆分为若干个互不相等的自然数之和，问如何拆分可以使得它们的乘积最大？从小到大输出。
∵ 若1作因数,则显然乘积不会最大.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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);
}
}
假设地球上的新生资源按恒定速度增长。照此测算，地球上现有资源加上新生资源可供x亿人生活a年，或供y亿人生活b年。( x > y，a < b，ax < by )
设现有资源为z，再生速度为v（即一年所生资源可养活v亿人），则为避免资源枯竭，最多养活v亿人。z + v × a = x × a z + v \times a = x \times a z + v × a = x × a z + v × b = y × b z + v \times b = y \times b z + v × b = y × b v × ( a − b ) = x × a − y × b v\times (a-b)=x\times a-y\times b v × ( a − b ) = x × a − y × b v = ( x × a − y × b ) / ( a − b ) v=(x\times a-y\times b)/(a-b) v = ( x × a − y × b ) / ( a − b )
1
2
3
4
5
6
7
8
#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));
}
给出一个等差数列的前两项a1，a2，求第n项是多少。
这个还用说么，O__O"… 不愧是小学数学
1
2
3
4
5
6
7
8
#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));
}
不超过n位的正整数中，有多少个回文数？(n<=10)
一位数：1,2,3,...,99 × 1 0 ( n − 1 ) / 2 9\times 10^{(n-1)/2} 9 × 1 0 ( n − 1 ) / 2
1
2
3
4
5
6
7
8
9
10
#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);
}
李白街上走，提壶去打酒。遇店加一倍，见花喝一斗。n遇店和花，喝光壶中酒。试问壶中原有多少酒？
O(n)的暴力( ( ( x × 2 − 1 ) × 2 − 1 ) × 2 − 1 ) × 2 − 1 . . . = 0 (((x\times 2-1)\times 2-1)\times 2-1)\times 2-1...=0 ( ( ( x × 2 − 1 ) × 2 − 1 ) × 2 − 1 ) × 2 − 1 . . . = 0
1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
using namespace std ;
int n;
float ans;
int main ()
{
scanf ("%d" ,&n);
while (n--)
ans=(ans+1 )/2.0 ;
printf ("%.5f" ,ans);
}
给定两个正整数a，b（a < b <= 10000）。求连乘积：
求从a~b中，每个数的质因数中有几个2，几个5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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个。。。。。。
1
2
3
4
5
6
7
8
#include <cstdio>
using namespace std ;
int main ()
{
int n;
scanf ("%d" ,&n);
printf ("%d" ,n*(n+1 )/2 );
}
两个质数的和是S，它们的积最大是多少？
尽量往中间靠，积最大，枚举判断是不是质数就好了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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 ;
}
}
}
两个正整数的最大公约数是G，最小公倍数是L，它们的和最小是多少？
∵gcd(x,G*L/x)=G ①
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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 ;}
}
}
有一个序列，初始时只有两个数x和y，之后每次操作时，在原序列的任意两个相邻数之间插入这两个数的和，得到新序列。举例说明：
n<=10 可以直接暴力。。。A n = A n − 1 × 3 − 1 An = An-1 \times 3 - 1 A n = A n − 1 × 3 − 1 A n − 1 / 2 = 3 × ( A n − 1 − 1 / 2 ) An - 1/2 = 3 \times ( A_{n-1} - 1/2 ) A n − 1 / 2 = 3 × ( A n − 1 − 1 / 2 ) A n = 3 / 2 × 3 n − 1 + 1 / 2 = ( 3 n + 1 ) / 2 An = 3/2 \times 3^{n-1} + 1/2 = ( 3^n + 1 ) / 2 A n = 3 / 2 × 3 n − 1 + 1 / 2 = ( 3 n + 1 ) / 2 a n s = A n × ( x + y ) ans = An \times (x+y) a n s = A n × ( x + y )
1
2
3
4
5
6
7
8
#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));
}
分数a/b化为小数后，小数点后第n位的数字是多少？
手推的
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......
1
2
3
4
5
6
7
8
9
10
11
12
13
#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);
}
假设今天是星期日，那么过a^b天之后是星期几？
暴力。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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" );
}
分母不超过 N 且 小于 A/B 的最大最简分数是多少？
x/y < A/B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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);
}
幂a^b的末3位数是多少？
mod 1000 算呗
1
2
3
4
5
6
7
8
9
10
#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);
}
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
我确实不知道我写的是个啥。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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);
}
