首页 > 代码库 > Codeforces 476D Dreamoon and Sets 规律+构造
Codeforces 476D Dreamoon and Sets 规律+构造
题目链接:点击打开链接
题意:
输出n组集合,每组4个。
对于任意一组中的4个元素,一组内任意2个数的gcd==k
且n组的所有数字各不相同。
要使得n组中最大的数字最小。
问:
输出最大的那个数,并输出n组的数字。
思路:
首先能得到,当把这组数字都/k,则任意两个数互质。
然后就是规律:
1 2 3 5
7 8 9 11
对应+6
#include <cstdio> #include <iostream> #include <cstring> #include <queue> #include <algorithm> #include <map> #include <set> #include <cmath> template <class T> inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; typedef long long ll; #define N 200010 const ll mod = 1000000007; ll n, k, ans; vector<ll>G[10001]; ll gcd(ll a, ll b){ if(a>b)swap(a,b); while(a){ b %= a; swap(a,b); } return b; } void solve(int x){ G[x].clear(); if(x==1){ G[x].push_back(1); G[x].push_back(2); G[x].push_back(3); G[x].push_back(5); } else { G[x].push_back(G[x-1][0]+6); G[x].push_back(G[x-1][1]+6); G[x].push_back(G[x-1][2]+6); G[x].push_back(G[x-1][3]+6); } } int main() { while(cin>>n>>k){ ans = 1; for(int i = 1; i <= n; i++)solve(i); pt((G[n][3])*k); puts(""); for(int i = 1; i <= n; i++){ for(int j = 0; j < G[i].size(); j++){ pt(G[i][j] * k); j==G[i].size()-1 ? putchar('\n'):putchar(' '); } } } return 0; }
Codeforces 476D Dreamoon and Sets 规律+构造
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。