凉肝的比赛（最小因子）

数论，DP

• • C - Fadi and LCM CodeForces - 1285C
  • B - Just Eat It!(DP思想)

C - Fadi and LCM CodeForces - 1285C

Today, Osama gave Fadi an integer X, and Fadi was wondering about the minimum possible value of max(a,b) such that LCM(a,b) equals X. Both a and b should be positive integers.

LCM(a,b) is the smallest positive integer that is divisible by both a and b. For example, LCM(6,8)=24, LCM(4,12)=12, LCM(2,3)=6.

Of course, Fadi immediately knew the answer. Can you be just like Fadi and find any such pair?

Input
The first and only line contains an integer X (1≤X≤1012).

Output
Print two positive integers, a and b, such that the value of max(a,b) is minimum possible and LCM(a,b) equals X. If there are several possible such pairs, you can print any.

Examples
Input
2
Output
1 2
Input
6
Output
2 3
Input
4
Output
1 4
Input
1
Output
1 1

//拓展：a*b/(两者最大公约数)=最小公倍数 
//思路推理：为什么最小的组合是a*b==x 但是要保证 a与b互质 
规律：如果x不是质数（1和x）那么还有一组互质组合，且一定是最小（简）的 
举例：x=36，a=4，b=9，若变化为a=4，b=3，则依然可以整除但是x不是其最小公倍数，因为所乘数（9,12） 有了公倍数 3，所以（4,9）为最小（简）组合
因为是求最小公倍数所以所乘以的数字不能有公约数，而互质的组合可以避免该事情也是可以转化为其余全部组合的根本 
//x的每个组合可以默认是a*b=x转化而来要保证 a与b互质，因为这种形式是最简（小）的表达形式可将其转化为其余的组合，得到全部组合 
//比如3 8的最小公倍数是3*8=24,8*3=24,可以将其转化为3*(2*4),8*3,如此转化会导致组合变大但是最小公倍数不变因为公因数变化了 
//所以说互质的一组是最简（小）形式因此可以推出其为最小的因子#include
#include
using namespace std;
int main(){long long x;long long mi=10000000;long long a,b;cin>>x;long long item;
//	for(long long i=1;i<=x;i++){
//		if(i*i>=x){
//			item=i;
//			break;
//		}
//	}
//	if(item*item==x&&item!=1)item--;
//		for(item;item>0;item--){
//			if(x%item==0){
//				long long m=x/item;
//				long long f=__gcd(m,item);
//				if(f==1){
//			   	a=min(item,m);
//			   	b=m+item-a;
//				   break;
//				  }
//			   }
//			}for(long long i=1;i<=x;i++){if(x%i==0&&__gcd(i,x/i)==1){//规律：如果x不是质数那么还有一组互质组合，且一定是最小的 a=i;		//举例：x=36，a=4，b=9，若变化为a=4，b=3，则依然可以整除但是x不是最小公倍数，因为所乘数（9,12） 有了公倍数  b=x/i;}if(i*i>x)break;
}cout<<a<<" "<<b;return 0;
}

B - Just Eat It!(DP思想)

Today, Yasser and Adel are at the shop buying cupcakes. There are n cupcake types, arranged from 1 to n on the shelf, and there are infinitely many of each type. The tastiness of a cupcake of type i is an integer ai. There are both tasty and nasty cupcakes, so the tastiness can be positive, zero or negative.

Yasser, of course, wants to try them all, so he will buy exactly one cupcake of each type.

On the other hand, Adel will choose some segment [l,r] (1≤l≤r≤n) that does not include all of cupcakes (he can’t choose [l,r]=[1,n]) and buy exactly one cupcake of each of types l,l+1,…,r.

After that they will compare the total tastiness of the cupcakes each of them have bought. Yasser will be happy if the total tastiness of cupcakes he buys is strictly greater than the total tastiness of cupcakes Adel buys regardless of Adel’s choice.

For example, let the tastinesses of the cupcakes be [7,4,−1]. Yasser will buy all of them, the total tastiness will be 7+4−1=10. Adel can choose segments [7],[4],[−1],[7,4] or [4,−1], their total tastinesses are 7,4,−1,11 and 3, respectively. Adel can choose segment with tastiness 11, and as 10 is not strictly greater than 11, Yasser won’t be happy 😦

Find out if Yasser will be happy after visiting the shop.

Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.

The first line of each test case contains n (2≤n≤105).

The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109), where ai represents the tastiness of the i-th type of cupcake.

It is guaranteed that the sum of n over all test cases doesn’t exceed 105.

Output
For each test case, print “YES”, if the total tastiness of cupcakes Yasser buys will always be strictly greater than the total tastiness of cupcakes Adel buys regardless of Adel’s choice. Otherwise, print “NO”.

Example
Input
3
4
1 2 3 4
3
7 4 -1
3
5 -5 5
Output
YES
NO
NO
Note
In the first example, the total tastiness of any segment Adel can choose is less than the total tastiness of all cupcakes.

In the second example, Adel will choose the segment [1,2] with total tastiness 11, which is not less than the total tastiness of all cupcakes, which is 10.

In the third example, Adel can choose the segment [3,3] with total tastiness of 5. Note that Yasser’s cupcakes’ total tastiness is also 5, so in that case, the total tastiness of Yasser’s cupcakes isn’t strictly greater than the total tastiness of Adel’s cupcakes.

#include
#include
using namespace std;
long long a[11000];
int main(){long long t;cin>>t;while(t--){long long ma=-999999999;long long n;scanf("%lld",&n);long long item=0,f=0,count=0,sum=0;for(int i=0;i<n;i++){scanf("%lld",&a[i]);sum+=a[i];if(item+a[i]>0){ //从局部推全局，一步一步递推出全局item+=a[i];f++;}else{item=0;f=0;}if(item>ma){ma=item;count=f;}}if(count!=n&&ma>=sum)printf("NO\n");else printf("YES\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！