电影下载网站模板,重庆建网站推广价格,建站平台营销,泉州网站建设哪家好4421. aplusb Time Limits: 1000 ms Memory Limits: 524288 KB Detailed Limits Goto ProblemSetDescription SillyHook要给小朋友出题了#xff0c;他想#xff0c;对于初学者#xff0c;第一题肯定是ab 啊#xff0c;但当他出完数据后神奇地发现.in不见了#xff0c… 4421. aplusb Time Limits: 1000 ms Memory Limits: 524288 KB Detailed Limits Goto ProblemSet Description SillyHook要给小朋友出题了他想对于初学者第一题肯定是ab 啊但当他出完数据后神奇地发现.in不见了只留下了一些.out他想还原.in但情况实在太多了于是他想要使得[a,b] ([a,b] 表示a,b 的最小公倍数)尽可能大。 Input 输入文件的第一行一个整数T 表示数据组数。接下来T行每行一个整数n 表示.out中的数值即abn 。 Output 共T行每行一个整数表示最大的[a,b] 的值。 Sample Input 3234 Sample Output 123 Data Constraint 30%的数据满足 T10,n1000100% 的数据满足T10000 ,n10^9 做法实际是一道结论题但我不会证明我用比较暴力的方法也过了。。。 显然a和b的值越接近越好于是把令p n / 2 1然后往后枚举找到的第一个 gcd(i, n - i) 1 的就是答案。 代码如下 1 #include cstdio2 #include iostream3 #include cstring4 #include cmath5 #define LL long long6 using namespace std;7 LL n, Q;8 9 inline LL read(){
10 LL s0; char chgetchar();
11 for(;ch0||ch9;chgetchar());
12 for(;ch0ch9;ss*10ch-0,chgetchar());
13 return s;
14 }
15
16 inline LL Gcd(LL x, LL y){
17 for (; y ! 0; ){
18 swap(x, y);
19 y y % x;
20 }
21 return x;
22 }
23
24
25 inline void Gets(){
26 LL pn1|1;
27 for(register int ip;in;i){
28 LL g Gcd(i, n - i);
29 if (g1){
30 printf(%lld\n,i*(n-i));
31 return;
32 }
33 }
34 }
35
36 int main(){
37 Qread();
38 for(;Q--;){
39 nread();
40 Gets();
41 }
42 } View Code 转载于:https://www.cnblogs.com/traveller-ly/p/9506007.html
