「LGOJ」Davor

题意

在征服南极之后,Davor 开始了一项新的挑战。下一步是在西伯利亚、格林兰、挪威的北极圈远征。他将在 20182018 年 12 月 31 日开始出发,在这之前需要一共筹集 $n$ 元钱。他打算在每个星期一筹集$x$ 元,星期二筹集 $x+k$ 元,……,星期日筹集 $x+6k$元,并在 52 个星期内筹集完。其中 $x,k$ 为正整数,并且满足 $1\le x\le 100$。

现在请你帮忙计算 $x,k$为多少时,能刚好筹集 $n $元。

如果有多个答案,输出 x尽可能大,k尽可能小的,注意 $k$必须大于 0。

Link

题解

这道题的关键是不定方程

不定方程:形如$ax+by=c$$(a,b,c均为常数,且a,b均不为0)$,一般情况下,每一个x的值都有一个y值和它相对应,有无穷多组解。如果方程(组)中,解的数值不能唯一确定,这样的方程(组)称为不定方程。

根据题意,我们可算出来一周的钱数是:

并且在52周内筹完

所以n必为52的倍数,我们把$n/=52$

然后我们再$n/=7$

于是乎我们可以在$[1,100]$中枚举$x$了

解方程,$x\le 100;k>0$

说说怎么推k的

设$\frac{n}{364}=p$

Code

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
#include <bits/stdc++.h>
using namespace std;

#define RE register

inline void fread(int &x){
x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=f;
}

int main(){
int n;
fread(n);
n/=364;
for(RE int i=100;i>=0;i--){
if((n-i)%3==0&&i<n){
printf("%d\n%d\n",i,(n-i)/3);
return 0;
}
}
return 0;
}
0%