题解 U534159 【降价处理】

发表于 更新于 分类于 ， 阅读次数： 本文字数： 500 阅读时长 ≈ 2 分钟

题目链接：降价处理

关于题目：作为 T2，一道数学题。

应用算法：最基础的数论。

\(\qquad\!\!\)这道题的题意还算明确，正解也非常好想，就是所有 \(w_i\) 的 \(\gcd\)。

\(\qquad\!\!\)我们考虑证明这个命题：（设每天在这 \(n\) 家子公司内该商品单价最高的所有家公司需将单价减少此时在这 \(n\) 家子公司内该商品单价最低的子公司该商品的单价）

\(\qquad\!\!\)设最后每家子公司的单价都降为 \(r\)，则倒推出在最后一次降价前一定为 \(k\)（一个正整数）家子公司的单价为 \(2r\)。

\(\qquad\!\!\)我们继续倒着向前推，对于第 \(i\) 次降价，被改动的最大单价原来为第 \(i+1\) 次降价前的两个单价之和，根据在第 \(i+1\) 次降价前所有的单价都为 \(w_i=k_ir\)（\(k_i\) 为一个正整数），那么第 \(i\) 次降价前的所有单价也都是 \(r\) 的正整数倍。

\(\qquad\!\!\)到这里我们证明了 \(r\) 为 \(w_i\) 的公约数，但是为什么一定是 \(\gcd\) 呢？因为任意两个正整数辗转相除/更相减损的得数不可能比这两个数的 \(\gcd\) 小，对于这 \(n\) 个单价也是这样，所以 \(r\) 一定为所有的 \(w_i\) 的 \(\gcd\)。

\(\qquad\!\!\)至此，我们证毕这道题的答案为所有\(w_i\) 的 \(\gcd\)。

\(\qquad\!\!\)代码（码风不喜勿喷）：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
int n,w,ans;
in int qread()
//快读
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
//快写
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in int gcd(re int x,re int y)
{
	return y?gcd(y,x%y):x;
}
int main()
{
	n=qread();
	ans=qread();
	for(re int i=2;i<=n;i++)
	{
		w=qread();
		ans=gcd(ans,w);
        //求 gcd
	}
	qwrite(ans);
    //输出 gcd
	putchar('\n');
	return 0;
}