Codeforces 837 E Vasya's Function
2024-08-25 22:20:40
Discription
Vasya is studying number theory. He has denoted a function f(a, b) such that:
- f(a, 0) = 0;
- f(a, b) = 1 + f(a, b - gcd(a, b)), where gcd(a, b) is the greatest common divisor of a and b.
Vasya has two numbers x and y, and he wants to calculate f(x, y). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.
Input
The first line contains two integer numbers x and y (1 ≤ x, y ≤ 1012).
Output
Print f(x, y).
Example
Input
3 5
Output
3
Input
6 3
Output
1 水水数论,可以发现随着运算的过程,gcd单调不减,所以我们可以每次处理gcd相同的一段。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll num[21],N=0,mn;
ll a,b,d,ans=0,A,B; ll gcd(ll x,ll y){
return y?gcd(y,x%y):x;
} inline void dvd(ll x){
for(int i=2;i*(ll)i<=x;i++) if(!(x%i)){
num[++N]=i;
while(!(x%i)) x/=i;
if(x==1) break;
}
if(x!=1) num[++N]=x;
} inline void solve(){
dvd(a); d=gcd(a,b);
while(b){
A=a/d,B=b/d,mn=1ll<<60;
if(A==1){
ans+=B;
break;
} for(int i=1;i<=N;i++) if(!(A%num[i])) mn=min(mn,B%num[i]);
ans+=mn,b-=mn*d,d=gcd(b,a);
} printf("%I64d\n",ans);
} int main(){
scanf("%I64d%I64d",&a,&b);
solve();
return 0;
}
最新文章
- 文本域的宽度和高度应该用cols和rows来控制,还是 用width和height来控制
- [Oracle] SQL*Loader 详细使用教程(3)- 控制文件
- seaJS学习资料参考
- fast_recovery_area无剩余空间(ORA-19815)
- Controller的激活
- 简单的理解deflate算法
- 入坑以来最清晰的this指南[老哥们来交流指正]
- Java 9 揭秘(5. 实现服务)
- MockMvc模拟对controller进行单元测试
- Linux第三节课学习笔记
- gitlab 之 cicd
- asp.net-常用服务器控件-20180329
- 周末时间学习Linux
- Pytorch Visdom
- Linux基础命令---lpstat查看打印任务
- Java并发编程笔记之Semaphore信号量源码分析
- Hash算法解决冲突的方法
- ODPS_ele—UDF Python API
- CentOS静默安装Oracle 11gR2(x64)
- ubuntu14安装redis