网站动态加速,福田网站建设费用,wordpress中文名字注册,家装设计软件哪个好用传送门
题意#xff1a; 给一个数组aiia_iiaii#xff0c;每次可以进行操作ax⌈axay⌉a_x\left \lceil \frac{a_x}{a_y} \right \rceilax⌈ayax⌉#xff0c;操作不能超过n5n5n5次#xff0c;最终需要把数组中的数变成n−1n-1n−1个111和一个222。
思路#x…传送门
题意 给一个数组aiia_iiaii每次可以进行操作ax⌈axay⌉a_x\left \lceil \frac{a_x}{a_y} \right \rceilax⌈ayax⌉操作不能超过n5n5n5次最终需要把数组中的数变成n−1n-1n−1个111和一个222。
思路 比较显然的是数组中原来的111和222是不需要操作的可以把222当做最终的222让后可以以ana_nan为分母让前面222的数都除ana_nan但是这个样子的话ana_nan就需要用222来消除但是操作明显不够。那么我们考虑一下n\sqrt{n}n,显然我们可以用n\sqrt{n}n当做分母an⌈anan⌉a_n\left \lceil \frac{a_n}{a_{\sqrt{n}}} \right \rceilan⌈anan⌉进行两次即可将ana_nan化成111。而n447\sqrt{n}447n447用222来消除的话还是有点不够我们可以继续开根号我们发现从2e52e52e5开根号开到222的最后一个最多只有5个根号数假设为a b c d e 。对于e我们可以ae⌈aead⌉a_e\left \lceil \frac{a_e}{a_d} \right \rceilae⌈adae⌉进行两次。对于每个根号数都这样操作最多需要10次让后对于不是根号数的直接以ana_nan作为分母一步到位。当根号数为5的时候操作数为10n−2−5n310n-2-5n310n−2−5n3满足题意。 还有注意是上取整开根号的时候注意判断是否为平方数我为了方便直接把每个平方根都1了。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int s[20],tot;
vectorPIIv;
bool st[N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--){scanf(%d,n);int nnn; v.clear(); tot0;while(nn2) st[nn]true,s[tot]nn,nn(int)sqrt(nn)1;for(int i3;in;i){if(st[i]) continue;v.pb({i,n});}for(int i1;itot;i){v.pb({s[i],s[i1]});v.pb({s[i],s[i1]});}v.pb({s[tot],2});v.pb({s[tot],2});printf(%d\n,(int)v.size());for(int i0;i(int)v.size();i) printf(%d %d\n,v[i].X,v[i].Y);for(int i1;itot;i) st[s[i]]false;}return 0;
}
/**/
