影视网站seo描述,友情链接怎么连,十大经典事件营销案例分析,淘宝客网站的建设G-Greater Integer, Better LCM
看到校大佬的代码就瞬间会做了。
当时和队友想的是#xff0c;首先转化题意即找两个数x≥a,y≥b[lcm(a,b)c]x\ge a,y\ge b[\text{lcm}(a,b)c]x≥a,y≥b[lcm(a,b)c]#xff0c;首先不考虑x≥a,y≥bx\ge a,y\ge bx≥a,y≥b的限制#xff0c;显…G-Greater Integer, Better LCM
看到校大佬的代码就瞬间会做了。
当时和队友想的是首先转化题意即找两个数x≥a,y≥b[lcm(a,b)c]x\ge a,y\ge b[\text{lcm}(a,b)c]x≥a,y≥b[lcm(a,b)c]首先不考虑x≥a,y≥bx\ge a,y\ge bx≥a,y≥b的限制显然对于cp1q1p2q2…pnqncp_1^{q_1}p_2^{q_2}\dots p_n^{q_n}cp1q1p2q2…pnqn考虑其中一项piqip_i^{q_i}piqi对于该项显然要么[pi0]a,[piqi]b[p_i^{0}]_a,[p_i^{q_i}]_b[pi0]a,[piqi]b要么[piqi]a,[pi0]b[p_i^{q_i}]_a,[p_i^{0}]_b[piqi]a,[pi0]b这样只需要暴搜就行了时间复杂度为O(2n)O(2^n)O(2n)但是加上了这个限制就不知道怎么搞了。
题目中有一个非常重要的地方就是∑qi≤18\sum q_i\leq 18∑qi≤18这意味这我们不需要考虑是[pi0]a,[piqi]b[p_i^{0}]_a,[p_i^{q_i}]_b[pi0]a,[piqi]b还是[piqi]a,[pi0]b[p_i^{q_i}]_a,[p_i^{0}]_b[piqi]a,[pi0]b只需要暴力枚举每一个qiq_iqi的次幂最后只针对x≥a,y≥bx\ge a,y\ge bx≥a,y≥b考虑即可。 详细看代码
最后一部分就是枚举超集dp转化一下。
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
void print(__int128 v)
{if(v0) return puts(0),void();string ans;while(v){ans.push_back(v%100);v/10;}reverse(ans.begin(),ans.end());printf(%s\n,ans.c_str());
}
ll p[25],q[25];
int n;
__int128 a,b;
__int128 fa[(118)5],fb[(118)5];
void dfs(int u,int s,__int128 cur)
{if(cura) fa[s]min(fa[s],cur);if(curb) fb[s]min(fb[s],cur);if(un) return;dfs(u1,s,cur);for(int i1;iq[u];i) {cur*p[u];dfs(u1,s,cur);}cur*p[u];dfs(u1,s^(1u),cur);
}
int main()
{nrd();for(int i0;in;i) p[i]rdll(),q[i]rdll();ard__int128(),brd__int128();memset(fa,0x3f,sizeof fa);memset(fb,0x3f,sizeof fb);dfs(0,0,1);__int128 ans; memset(ans,0x3f,sizeof ans);for(int i(1n)-1;i0;i--)for(int j0;jn;j)if((ij)1){fa[i^(1j)]min(fa[i^(1j)],fa[i]);fb[i^(1j)]min(fb[i^(1j)],fb[i]);}for(int i0;i(1n);i) ansmin(ans,fa[i]fb[((1n)-1)^i]-a-b);print(ans);return 0;
}
