Codeforces 1244C （数学）
题意描述
\(x+y+z=n\)
\(xw+yd=p\)
求是否有满足方程的解，无解则输出\(-1\)。
思路1（枚举）
由于\(d
思路2（exgcd）
发现方程\(xw+yd=p\)类似于\(xw+yd=gcd(w,d)\)的形式，我们可以利用\(exgcd\)求出系数\(x\)和\(y\)，如果\(p\%gcd!=0\)，则无解；否则方程的一组解为\(x*p/gcd\)和\(y*p/gcd\)。
由于我们求得的解要满足\(x+y+z=n\)，所以我们要对\(x\)和\(y\)进行适当的调整。题目中说明了\(w>d\)，所以要想\(x+y\)最小，我们可以对\(y\)进行调整让\(y\)最小，由于\(xw+yd=p\)，所以对y的增减即加减\(w/gcd\)，即y最小为\(y*k \% w/gcd\)，注意计算过程中对\(y\)进行取模。
AC代码1
#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#include "cassert"
#include "unordered_map"
#include "sstream"
#include "cstdio"
using namespace std;
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define rep(x,l,u) for(ll x=l;x=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);
#define seteps(N) setprecision(N)
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define lson (ind<<1)
#define rson (ind<<1|1)
#define endl '\n'
#define dbg(x) cerr << #x " = " << (x) << endl
#define mp make_pair
//#define LOCAL
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair PII;
typedef pair PCC;
typedef pair PDD;
typedef pair PLL;
typedef pair PIII;
struct Scanner {
bool hasNext = 1;
bool hasRead = 1;
int nextInt() {
hasRead = 0;
int res = 0;
char flag = 1, ch = getchar();
while(ch != EOF && !isdigit(ch)) {
hasRead = 1;
flag = (ch == '-') ? -flag : flag;
ch = getchar();
}
while(ch != EOF && isdigit(ch)) {
hasRead = 1;
res = res * 10 + (ch - '0');
ch = getchar();
}
if(ch == EOF)
hasNext = 0;
return res * flag;
}
ll nextLL() {
hasRead = 0;
ll res = 0;
char flag = 1, ch = getchar();
while(ch != EOF && !isdigit(ch)) {
hasRead = 1;
flag = (ch == '-') ? -flag : flag;
ch = getchar();
}
while(ch != EOF && isdigit(ch)) {
hasRead = 1;
res = res * 10 + (ch - '0');
ch = getchar();
}
if(ch == EOF)
hasNext = 0;
return res * flag;
}
char nextChar() {
hasRead = 0;
char ch = getchar();
while(ch != EOF && isspace(ch)) {
hasRead = 1;
ch = getchar();
}
if(ch == EOF)
hasNext = 0;
return ch;
}
int nextString(char *str) {
hasRead = 0;
int len = 0;
char ch = getchar();
while(ch != EOF && isspace(ch)) {
hasRead = 1;
ch = getchar();
}
while(ch != EOF && !isspace(ch)) {
hasRead = 1;
str[++len] = ch;
ch = getchar();
}
str[len + 1] = 0;
if(ch == EOF)
hasNext = 0;
return len;
}
} sc;
ll rd() {
ll x = sc.nextLL();
return x;
}
void rd(int &x) {
x = sc.nextInt();
}
void rd(ll &x) {
x = sc.nextLL();
}
void rd(char &x) {
x = sc.nextChar();
}
void rd(char* x) {
sc.nextString(x);
}
template
void rd(pair &x) {
rd(x.first);
rd(x.second);
}
template
void rd(T *x, int n) {
for(int i = 1; i <= n; ++i)
rd(x[i]);
}
template
void rd(vector &x,int n){
for(int i = 1; i <= n; ++i)
rd(x[i]);
}
void printInt(int x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10)
printInt(x / 10);
putchar('0' + x % 10);
}
void printLL(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10)
printLL(x / 10);
putchar('0' + x % 10);
}
void pr(int x, char ch = '\n') {
printInt(x);
putchar(ch);
}
void pr(ll x, char ch = '\n') {
printLL(x);
putchar(ch);
}
template
void pr(pair x, char ch = '\n') {
#ifdef LOCAL
putchar('<');
pr(x.first, ' ');
pr(x.second, '>');
putchar(ch);
return;
#endif //LOCAL
pr(x.first, ' ');
pr(x.second, ch);
}
template
void pr(T *x, int n) {
for(int i = 1; i <= n; ++i)
pr(x[i], " \n"[i == n]);
}
template
void pr(vector &x) {
int n = x.size();
for(int i = 1; i <= n - 1; ++i)
pr(x[i], " \n"[i == n - 1]);
}
const int N=105;
const int M=1<<12;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
ll n,p,d,w;
struct Solver
{
void InitOnce(){
}
void Read(){
rd(n);
rd(p);
rd(w);
rd(d);
}
void Solve(){
rep(i,0,w){
ll cur=p-i*d;
if(cur%w || cur<0) continue;
ll win=cur/w;
if(win+i<=n){
pr(win,' ');
pr(i,' ');
pr(n-win-i);
return;
}
}
pr(-1);
}
}solver;
int main(){
#ifdef LOCAL
freopen("data.in","r",stdin);
#endif //LOCAL
solver.InitOnce();
int t=1;
//t=sc.nextInt();
//t=INF;
while(t--){
solver.Read();
if(!sc.hasRead) break;
solver.Solve();
if(!sc.hasNext) break;
}
}
AC代码2
#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#include "cassert"
#include "unordered_map"
#include "sstream"
#include "cstdio"
using namespace std;
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define rep(x,l,u) for(ll x=l;x=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);
#define seteps(N) setprecision(N)
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define lson (ind<<1)
#define rson (ind<<1|1)
#define endl '\n'
#define dbg(x) cerr << #x " = " << (x) << endl
#define mp make_pair
//#define LOCAL
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair PII;
typedef pair PCC;
typedef pair PDD;
typedef pair PLL;
typedef pair PIII;
struct Scanner {
bool hasNext = 1;
bool hasRead = 1;
int nextInt() {
hasRead = 0;
int res = 0;
char flag = 1, ch = getchar();
while(ch != EOF && !isdigit(ch)) {
hasRead = 1;
flag = (ch == '-') ? -flag : flag;
ch = getchar();
}
while(ch != EOF && isdigit(ch)) {
hasRead = 1;
res = res * 10 + (ch - '0');
ch = getchar();
}
if(ch == EOF)
hasNext = 0;
return res * flag;
}
ll nextLL() {
hasRead = 0;
ll res = 0;
char flag = 1, ch = getchar();
while(ch != EOF && !isdigit(ch)) {
hasRead = 1;
flag = (ch == '-') ? -flag : flag;
ch = getchar();
}
while(ch != EOF && isdigit(ch)) {
hasRead = 1;
res = res * 10 + (ch - '0');
ch = getchar();
}
if(ch == EOF)
hasNext = 0;
return res * flag;
}
char nextChar() {
hasRead = 0;
char ch = getchar();
while(ch != EOF && isspace(ch)) {
hasRead = 1;
ch = getchar();
}
if(ch == EOF)
hasNext = 0;
return ch;
}
int nextString(char *str) {
hasRead = 0;
int len = 0;
char ch = getchar();
while(ch != EOF && isspace(ch)) {
hasRead = 1;
ch = getchar();
}
while(ch != EOF && !isspace(ch)) {
hasRead = 1;
str[++len] = ch;
ch = getchar();
}
str[len + 1] = 0;
if(ch == EOF)
hasNext = 0;
return len;
}
} sc;
ll rd() {
ll x = sc.nextLL();
return x;
}
void rd(int &x) {
x = sc.nextInt();
}
void rd(ll &x) {
x = sc.nextLL();
}
void rd(char &x) {
x = sc.nextChar();
}
void rd(char* x) {
sc.nextString(x);
}
template
void rd(pair &x) {
rd(x.first);
rd(x.second);
}
template
void rd(T *x, int n) {
for(int i = 1; i <= n; ++i)
rd(x[i]);
}
template
void rd(vector &x,int n){
for(int i = 1; i <= n; ++i)
rd(x[i]);
}
void printInt(int x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10)
printInt(x / 10);
putchar('0' + x % 10);
}
void printLL(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10)
printLL(x / 10);
putchar('0' + x % 10);
}
void pr(int x, char ch = '\n') {
printInt(x);
putchar(ch);
}
void pr(ll x, char ch = '\n') {
printLL(x);
putchar(ch);
}
template
void pr(pair x, char ch = '\n') {
#ifdef LOCAL
putchar('<');
pr(x.first, ' ');
pr(x.second, '>');
putchar(ch);
return;
#endif //LOCAL
pr(x.first, ' ');
pr(x.second, ch);
}
template
void pr(T *x, int n) {
for(int i = 1; i <= n; ++i)
pr(x[i], " \n"[i == n]);
}
template
void pr(vector &x) {
int n = x.size();
for(int i = 1; i <= n - 1; ++i)
pr(x[i], " \n"[i == n - 1]);
}
const int N=105;
const int M=1<<12;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
ll n,p,d,w;
struct Solver
{
void InitOnce(){
}
void Read(){
rd(n);
rd(p);
rd(w);
rd(d);
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1,y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
void Solve(){
ll x=0,y=0;
ll gcd=exgcd(w,d,x,y);
if((p%gcd)==0){
ll k=p/gcd;
ll m=w/gcd;
y=((y%m)*(k%m)%m+m)%m;
x=(p-y*d)/w;
if(x>=0 && y>=0 && x+y<=n){
pr(x,' ');
pr(y,' ');
pr(n-x-y);
return;
}
}
pr(-1);
}
}solver;
int main(){
#ifdef LOCAL
freopen("data.in","r",stdin);
#endif //LOCAL
solver.InitOnce();
int t=1;
//t=sc.nextInt();
//t=INF;
while(t--){
solver.Read();
if(!sc.hasRead) break;
solver.Solve();
if(!sc.hasNext) break;
}
}