[XSY] 简单的数论题（数学、构造）
简单的数论题
m(a3+b3)=n(c3+d3)m(a^3+b^3)=n(c^3+d^3)m(a3+b3)=n(c3+d3)
考虑因式分解(a3+b3),(c3+d3):考虑因式分解(a^3+b^3),(c^3+d^3):考虑因式分解(a3+b3),(c3+d3):
a3+b3=(a+b)3−3ab(a+b)=(a+b)(a2+b2−ab)a^3+b^3=(a+b)^3-3ab(a+b)=(a+b)(a^2+b^2-ab)a3+b3=(a+b)3−3ab(a+b)=(a+b)(a2+b2−ab)
c3+d3=(c+d)3−3cd(c+d)=(c+d)(c2+d2−cd)c^3+d^3=(c+d)^3-3cd(c+d)=(c+d)(c^2+d^2-cd)c3+d3=(c+d)3−3cd(c+d)=(c+d)(c2+d2−cd)
∴m(a+b)(a2+b2−ab)=n(c+d)(c2+d2−cd)\therefore m(a+b)(a^2+b^2-ab)=n(c+d)(c^2+d^2-cd)∴m(a+b)(a2+b2−ab)=n(c+d)(c2+d2−cd)
等式两边带着系数m,n很不方便，(a2+b2−ab),(c2+d2−cd)结构较复杂，等式两边带着系数m,n很不方便，(a^2+b^2-ab),(c^2+d^2-cd)结构较复杂，等式两边带着系数m,n很不方便，(a2+b2−ab),(c2+d2−cd)结构较复杂，
考虑用(a+b),(c+d)把m,n消掉：考虑用(a+b),(c+d)把m,n消掉：考虑用(a+b),(c+d)把m,n消掉：
令a+b=kn,c+d=km令a+b=kn,c+d=km令a+b=kn,c+d=km
∴a2+b2−ab=c2+d2−cd①\therefore a^2+b^2-ab=c^2+d^2-cd①∴a2+b2−ab=c2+d2−cd①
尽量让左式出现(a+b)，右式出现(c+d):尽量让左式出现(a+b)，右式出现(c+d):尽量让左式出现(a+b)，右式出现(c+d):
(a+b)2−3ab=(c+d)2−3cd(a+b)^2-3ab=(c+d)^2-3cd(a+b)2−3ab=(c+d)2−3cd
k2n2−3ab=k2m2−3cdk^2n^2-3ab=k^2m^2-3cdk2n2−3ab=k2m2−3cd
k2(n2−m2)=3(ab−cd)k^2(n^2-m^2)=3(ab-cd)k2(n2−m2)=3(ab−cd)
考虑令k=3,构造3(n2−m2)=ab−cd②:考虑令k=3,构造3(n^2-m^2)=ab-cd②:考虑令k=3,构造3(n2−m2)=ab−cd②:
尝试1：令ab=3n2,cd=3m2，与a+b=3n,c+d=3m联立求解a,b,c,d尝试1：令ab=3n^2,cd=3m^2，与a+b=3n,c+d=3m联立求解a,b,c,d尝试1：令ab=3n2,cd=3m2，与a+b=3n,c+d=3m联立求解a,b,c,d
结果：方程无解结果：方程无解结果：方程无解
尝试2：因为已知(a+b),(c+d),考虑求出(a−b),(c−d):尝试2：因为已知(a+b),(c+d),考虑求出(a-b),(c-d):尝试2：因为已知(a+b),(c+d),考虑求出(a−b),(c−d):
回到①式，让左式出现(a−b)，右式出现(c−d)：回到①式，让左式出现(a-b)，右式出现(c-d)：回到①式，让左式出现(a−b)，右式出现(c−d)：
(a−b)2+ab=(c−d)2+cd(a-b)^2+ab=(c-d)^2+cd(a−b)2+ab=(c−d)2+cd
让此式向②式靠近：让此式向②式靠近：让此式向②式靠近：
(c−d)2−(a−b)2=ab−cd③(c-d)^2-(a-b)^2=ab-cd③(c−d)2−(a−b)2=ab−cd③
②③联立得：②③联立得：②③联立得：
(c−d)2−(a−b)2=3(n2−m2)(c-d)^2-(a-b)^2=3(n^2-m^2)(c−d)2−(a−b)2=3(n2−m2)
令u=c−d,v=a−b令u=c-d,v=a-b令u=c−d,v=a−b
u2−v2=3(n2−m2)u^2-v^2=3(n^2-m^2)u2−v2=3(n2−m2)
(u+v)(u−v)=3(n+m)(n−m)(u+v)(u-v)=3(n+m)(n-m)(u+v)(u−v)=3(n+m)(n−m)
把3放进其中一个括号中：把3放进其中一个括号中：把3放进其中一个括号中：
(u+v)(u−v)=(n+m)(3n−3m)(u+v)(u-v)=(n+m)(3n-3m)(u+v)(u−v)=(n+m)(3n−3m)
令u+v=n+m,u−v=3n−3m令u+v=n+m,u-v=3n-3m令u+v=n+m,u−v=3n−3m
解得u=2n−m,v=2m−n解得u=2n-m,v=2m-n解得u=2n−m,v=2m−n
由a+b=3n,a−b=2m−n得a=n+m,b=2n−m由a+b=3n,a-b=2m-n得a=n+m,b=2n-m由a+b=3n,a−b=2m−n得a=n+m,b=2n−m
由c+d=3m,c−d=2n−m得c=n+m,d=2m−n由c+d=3m,c-d=2n-m得c=n+m,d=2m-n由c+d=3m,c−d=2n−m得c=n+m,d=2m−n
如此，我们便构造出了一组整数解
考虑何时有正整数解：
2n−m>0,2m−n>02n-m>0,2m-n>02n−m>0,2m−n>0
∴nm∈(12,2)时所得为正整数解\therefore \frac{n}{m}\in(\frac{1}{2},2)时所得为正整数解∴mn∈(21,2)时所得为正整数解
若nm∉(12,2)\frac{n}{m}\not\in (\frac{1}{2},2)mn∈(21,2)，寻找p3nq3m∈(12,2)\frac{p^3n}{q^3m}\in(\frac{1}{2},2)q3mp3n∈(21,2)（令a,ba,ba,b变为原来的qqq倍，c,dc,dc,d变为原来的ppp倍）
为了方便，我们设n<mn<mn<m(否则的话swap(n,m)即可)
那么此时必然有0<nm<10<\frac{n}{m}<10<mn<1
若nm<14,nm←23nm若\frac{n}{m}<\frac{1}{4},\frac{n}{m}\leftarrow\frac{2^3n}{m}若mn<41,mn←m23n (保证变化后nm<2\frac{n}{m}<2mn<2)
若14<=nm<=12,nm←23n33m若\frac{1}{4}<=\frac{n}{m}<=\frac{1}{2},\frac{n}{m}\leftarrow\frac{2^3n}{3^3m}若41<=mn<=21,mn←33m23n (保证变化后12<nm<2\frac{1}{2}<\frac{n}{m}<221<mn<2)
若nm>12,保证有正整数解若\frac{n}{m}>\frac{1}{2},保证有正整数解若mn>21,保证有正整数解
总结：既然题目只要求一组解，那么就要大胆地作假设来方便自己的运算，大胆地凑答案
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int T,rev; ll n,m,a,b,c,d,p,q; void solve(){rev=0;p=q=1ll;if(n>m){swap(n,m);rev=1;}while(4ll*n<m){p*=2ll;n*=8ll;}if(2ll*n<=m){p*=3ll;n*=27ll;q*=2ll;m*=8ll;}a=q*(n+m);b=q*(2ll*n-m);c=p*(n+m);d=p*(2ll*m-n);if(rev) printf("%lld %lld %lld %lld\n",c,d,a,b);else printf("%lld %lld %lld %lld\n",a,b,c,d); } int main(){scanf("%d",&T);while(T--){n=read();m=read();solve();}return 0; }总结
以上是生活随笔为你收集整理的[XSY] 简单的数论题（数学、构造）的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： [XSY] 宝藏（LCS，DP）
- 下一篇： [XSY] 简单的博弈题（博弈+dp+组