当前位置: 首页 > news >正文

P1072 [NOIP 2009 提高组] Hankson 的趣味题

题目传送门

欢迎光顾我的博客

(下面称 \(V\)\(a_0,a_1,b_0,b_1\) 的值域)

我们在小学二年级就学过,对于两个正整数 \(a,b\) ,可以分别将它们表示为 \(mx,my\) ,其中 \(m=gcd(a,b),gcd(x,y)=1\)

我们借这条性质略微表示一下题目里的 \(x,a_0,a_1,b_0,b_1\)

\( \begin{cases} x=m_1x_1 \\ a_0=m_1y_1 \\ a_1=m_1 \\ x=m_2x_2 \\ b_0=m_2y_2 \\ b_1=m_2x_2y_2 \\ \end{cases} \)

然后我们发现有几个量是可以求的: \(m_1=a_1,x_2=b_1/b_0,y_1=a_0/a_1\)

接下来,我们考虑枚举 \(m_2\) ,这样剩下的 \(x_1,y_2\) 都可以求出来了。

正常来说,如果不质因数分解的话,从 \(1\) 逐个枚举到 \(b_0\) 的时间复杂度是 \(O(V)\) 的,无法接受。

但是我们小学二年级还学过, \(\sqrt b_0\) ~ \(b_0\) 的因子个数与 \(1\) ~ \(\sqrt b_0\) 的因子个数大致相等,可是 \(\sqrt b_0\) ~ \(b_0\) 的整数个数与 \(1\) ~ \(\sqrt b_0\) 就不是一个量级的。

所以我们枚举 \(1\) ~ \(\sqrt b_0\) 里的数,假设当前枚举到了某个因子 \(y\) ,那么 \(\sqrt b_0\) ~ \(b_0\) 里会存在一个数 \(z\) ,使得 \(y \times z = b_0\)。我们在枚举到 \(m_2=y\) 的时候顺带着算算 \(m_2=z\) 时是否有解就行了。

时间复杂度 \(O(n \sqrt V \log V)\)

代码:

P1072
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();}while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}inline void write(int x){if(x<0) putchar('-'),x=-x;if(x<10) putchar(x+'0');else write(x/10),putchar(x%10+'0');
}int T,A0,A1,B0,B1,M1,Y1,X2,ans;inline int gcd(int a,int b){return (b==0?a:gcd(b,a%b));
}inline int solve(int M2){//计算当前枚举的m2是否有解 int Y2=B0/M2;if(gcd(Y2,X2)>1){//x2,y2不互质时非法 return 0;}if(M2*X2%M1!=0){//x1不为整数时非法 return 0;}int X1=M2*X2/M1;if(gcd(X1,Y1)>1){//x1,y1不互质时非法 return 0;}return 1;
}signed main(){T=read();while(T--){ans=0;A0=read(),A1=read(),B0=read(),B1=read();M1=A1;X2=B1/B0;Y1=A0/A1;int i;for(i=1;i*i<B0;i++){if(B0%i==0){int res1=solve(B0/i);ans+=res1;int res2=solve(i);ans+=res2;}}if(i*i==B0){//b0是平方数的情况需要特判,因为放在循环里会算两次 int res=solve(i);ans+=res;}printf("%lld\n",ans);}return 0;
}
http://www.hskmm.com/?act=detail&tid=32510

相关文章:

  • 25w41a快照测评:鹦鹉螺成精了?长矛教你戳穿末影人!
  • Day15-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\classlei
  • Day14
  • window电脑开启hyperV虚拟化功能后导致本地服务端口被占用问题处理方案
  • RAG检索质量差?这5种分块策略帮你解决70%的问题
  • 初识pytorch:网络骨架中的填充之各种层
  • Day5字符型
  • 本地链路地址
  • 体育
  • Meta推出Agent Learning via Early Experience,推动语言代理自主学习新范式
  • Fiddler And LINQ - 特洛伊
  • 计算机视觉在自动化质检中的应用
  • 动态加速中优化失败路径反馈的方法
  • 铜价冲击下,如何“锁住”母排利润?
  • 前端快速开发工具推荐与实战 让开发速度提升 3 倍的完整工具链
  • js代码、js文件混淆、加密
  • Salesforce推出AI版Setup,说句话就能搞定配置?
  • 10.16读书报告
  • 火山引擎Data Agent再拓新场景,重磅推出用户研究Agent
  • 元推理:哥德尔搞不完定理,翻来覆去的搞。。。。
  • Matlab选择常见颜色
  • HyperWorks许可状态监控
  • 2025年纺丝机实力源头靠谱优质口碑厂家推荐,知名品牌纺丝机生产商哪家好?
  • 2025 年防静电地板源头厂家最新推荐榜单:权威品牌实力展现,助力各行业精准挑选优质产品
  • PostgreSQL社区CUUG 院校行 - 内蒙古农业大学计算机与信息工程学院
  • 2025 年激光焊锡源头厂家最新推荐排行榜:覆盖多行业需求,助力企业精准挑选优质设备供应商
  • 2025年西安买房攻略Top10:揭秘高性价比学区房与第四代住宅新趋势
  • 2025年西安购房热点:学区房与地铁盘终极指南
  • 2025年铝复合板厂家Top10排名:一站式服务引领行业新潮流
  • 2025年铝复合板厂家十大排名榜单:行业权威推荐与选择指南