本文主要是介绍Codeforces Round #272 (Div. 2) D,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
D. Dreamoon and Sets
题意:构造n个这样的集合,集合内有4个元素,它们两两的最大公约数等于k。所有集合不能包含相同的元素。问构造出来以后所有集合中最大元素的最小值是多少,并输出每个集合。
思路:稍微分析一下,如果只造一个集合,肯定是k的1,2,3,5倍。如果是多个集合,那么第i个集合的数可以是k的(i-1)*6+1,(i-1)*6+2,(i-1)*6+3,(i-1)*6+5倍。至于为什么,我也说不清楚,但是可以肯定的是,这4个数是两两互质的,因为它们之中只有一个偶数,肯定不会有公约数2;它们之中只有一个数能被3整除,也不会有公约数3;同样也不会有公约数4,5,6...而且这些数会很紧凑,至于为什么一定是最小的,我还证明不了,求大神指教。。。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#include <sstream>
#define INF 1000000000
#define ll long long
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010 using namespace std; int main(){ll n,k;while(cin>>n>>k){int ans=k*((n-1)*6+1+4);cout<<ans<<endl;for(int i=1;i<=n;i++){cout<<((i-1)*6+1)*k<<" "<<((i-1)*6+2)*k<<" "<<((i-1)*6+3)*k<<" "<<((i-1)*6+5)*k<<endl;}}return 0;
}
这篇关于Codeforces Round #272 (Div. 2) D的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!