可惜cf不能用int128,不然这个题就是个exgcd的板子题

这是exgcd的解法,但是只用ll的话会溢出

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll x,y,z,a,b,c,d,n; ll exgcd(ll a,ll b,ll &x,ll &y){//返回(a,b)
if(b==){x=,y=;return a;}
ll d=exgcd(b,a%b,x,y);
ll z=x;x=y,y=z-a/b*y;
return d;
} int main(){
cin>>n>>c>>a>>b;//1e12,c:1e17,a:1e5,b:1e5
d=__gcd(a,b);
if(c%d!=){
puts("-1");return ;
} exgcd(a,b,x,y);
//923399641127 50915825165227299 94713 49302
x*=c/d;y*=c/d;
ll mod1=b/d,mod2=a/d; //先让x,y都变成非负整数
if(x<){
ll k;
if(x%mod1==)k=abs(x/mod1);
else k=abs(x/mod1)+;
x+=k*mod1;
y-=k*mod2;
}
else if(y<){
ll k;
if(y%mod2==)k=abs(y/mod2);
else k=abs(y/mod2)+;
x-=k*mod1;
y+=k*mod2;
} if(x< || y<){
puts("-1");return ;
}
if(x>n && y>n){
puts("-1");return ;
}
//让x+y的值取到最小值
if(mod1>mod2){
ll k=x/mod1;
x-=k*mod1;
y+=k*mod2;
}
else {
ll k=y/mod2;
x+=k*mod1;
y-=k*mod2;
}
if(x+y>n){puts("-1");return ;}
cout<<x<<" "<<y<<" "<<n-x-y<<"\n";
}

这是直接枚举的办法

/*
ax+by=c;
x+y+z=n;
b<a<=1e5; c<=1e17; n<=1e12
性质:如果有解,那么一定有y<a的一个解
假设有解 (x,y=y'+a)
ax+b(y'+a)=c
ax+by'+ba=c;
a(x+b)+by'=c,即必定有一个解是(x+b,y')
所以枚举y=[0,a-1]即可
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a,b,c;
int main(){
cin>>n>>c>>a>>b;
for(ll y=;y<a;y++){
ll t=c-b*y;
if((t>=) && t%a==){
ll x=t/a;
if(x+y<=n){
cout<<x<<" "<<y<<" "<<n-x-y;
return ;
}
}
}
puts("-1");
}

最新文章

  1. 在PHP中使用Mysqli操作数据库
  2. 用MVC的辅助方法自定义了两个控件:“可编辑的下拉框控件”和“文本框日历控件”
  3. C# 正则表达式测试工具与分享窗体自适应类
  4. HttpResponse对象
  5. iOS block里的self
  6. javascript高级编程运用
  7. 关于Function()函数对象的那些小九九
  8. Linux文本操作三大利器总结:sed、awk、grep
  9. Commons Codec基本使用(转载)
  10. Node.js_express_route 路由
  11. RabbitMq相关
  12. 区块链会与io域名有什么关系
  13. 用二分法定义平方根函数(Bisection method Square Root Python)
  14. vue之递归组件实现树形目录
  15. [trick] 玩弄svn的目录结构
  16. pytorch总结
  17. Android Studio常用设置
  18. [Hook] 跨进程 Binder设计与实现 - 设计篇
  19. mysql zerofill 的使用
  20. mysql 权限管理 grant 命令

热门文章

  1. magento 站内优化和站外优化详解
  2. JVM&amp;GC
  3. Python基础教程(007)--Python的优缺点
  4. 树状数组,Fenwick Tree
  5. Tomcat集群搭建超详细(apache+mod_jk+tomcat)
  6. scrapy入门实战-爬取代理网站
  7. PIL库,图像处理第三方库
  8. 用 Flask 来写个轻博客 (16) — MV(C)_Flask Blueprint 蓝图
  9. angular5引入sass
  10. 实习记——《Rethink》