洛谷 P5596 【XR-4】题 题解
2024-09-05 02:02:49
本题只要 推式子 就可以了。
\[y^2-x^2=ax + b
\]
\]
\[a x + x^2 = y^2 - b
\]
\]
\[4 x^2 + 4 ax = 4 y^2 - 4b
\]
\]
\[(2x+a)^2-a^2=4y^2-4b
\]
\]
\[(2x+a)^2-4y^2=a^2-4b
\]
\]
\[(2x+a+2y)(2x+a-2y)=a^2-4b
\]
\]
到这里,式子推完了。 用到了一些因式分解、配方、移项等的知识,应该不算难吧。
而我们已知 \(a\) 和 \(b\).
此时只需要枚举 \(a^2-4b\) 的因子个数。但你会发现,不是所有的因子都可以满足 有正整数解的。
比方说现在 \(a^2-4b=u \times v(u \leq \sqrt{a^2-4b})\),此时有:
\[2x+a-2y=u,2x+a+2y=v
\]
\]
即:
\[2x+a=\frac{u+v}{2},y=\frac{v-u}{4}
\]
\]
显然需要满足的是:
\[2|u+v , 4|v-u , u=a \bmod 2 , v=a \bmod 2
\]
\]
然后枚举即可。
时间复杂度: \(O(\sqrt {a^2-4b})\)
但是,对于\(a=10^8\),\(b=0\),很有可能会超时。
这时,观察两个性质:
\[u=a \bmod 2 , v=a \bmod 2
\]
\]
所以每次 \(u\) 和 \(v\) 的枚举 \(+2\) 即可。 也就是它们的奇偶性和\(a\)一样。
虽然常数上就是 \(\frac{1}{2}\) ,但是事实说明在超时的边缘,这还是很重要的。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int main(){
ll a=read(),b=read();
ll x=a*a-4*b,ans=0;
if(!x) {printf("inf");return 0;}
for(ll i=(a+1)%2+1;i*i<=abs(x);i+=2){
if(x%i) continue;
ll u=i,v=abs(x/i);
if(x<0) u=-u;
if((v-u)%4) continue;
if(v-(v-u)/2<a) break;
ans++;
}
printf("%lld\n",ans);
return 0;
}
最新文章
- (一)sql入门 导读
- 面试复习(C++)之归并排序
- 不可或缺 Windows Native (17) - C++: 类与对象
- java分层开发
- A/B测试
- 微信消息接收 验证URL有效性 C#代码示例
- LINUX内核笔记
- MySQL和PostgreSQL 导入数据对照
- 彻底理解position与anchorPoint - Wonderffee&#39;s Blog(转)
- (转)一步一步学习PHP(5)——类和对象
- Jenkins-FQA
- php Yii2 报错unexpected &#39;}&#39;
- ES系列十九、kibana基本查询、可视化、仪表盘用法
- VS NuGet加载本地程序包
- BZOJ4519 CQOI2016不同的最小割(最小割+分治)
- Ubuntu连接多台Ubuntu server的问题
- Autofac register and resolve
- 小于12px的字体大小在Chrome中不起作用
- 课时11.HTML基本机构详解(掌握)
- css字体font-family