2057. [ZLXOI2015]殉国

★☆ 输入文件：BlackHawk.in 输出文件：BlackHawk.out 评测插件
时间限制：0.05 s 内存限制：256 MB

【题目描述】

正义的萌军瞄准了位于南极洲的心灵控制器，为此我们打算用空袭摧毁心灵控制器，然而心灵控制器是如此强大，甚至能缓慢控制飞行员。一群勇敢的士（feng）兵（zi）决定投弹后自杀来避免心灵控制。然而自杀非常痛苦，所以萌军指挥官决定到达目的地后让飞机没油而坠落(也避免逃兵)。军官提供两种油：石油和中国输送来的地沟油,刚开始飞机没有油，飞机可以加几桶石油和几桶地沟油(假设石油和地沟油都有无限桶)，飞机落地时必须把油耗尽，已知一桶石油和一桶地沟油所能支撑的飞行距离分别为a,b,驾驶员们必须飞往一个目的地，总距离为c.

1.最少，最多需要加几桶油，若只有一种方案，最少和最多的是相同的.

2.总共有多少种不同的加油配方(死法)能到达目的地。

【输入格式】

只有一行，三个正整数a,b,c

【输出格式】

两行，第一行为最少加几次油和最多加几次油，

第二行为加油方法总数。

若不存在任何方法，第一行输出-1 -1

第二行输出0

【样例输入】

样例1：

2 3 10

样例2：

6 8 10

【样例输出】

样例1：

4 5

2

样例2：

-1 -1

0

【提示】

样例解释：

样例一：飞机加两次石油，两次地沟油，总次数为4，2*2+3*3=10

飞机加五次石油，不加地沟油，总次数为5,2*5+3*0=10

总共两种

样例二：飞机无法到达目的地

数据范围：

对于10%的数据,a<=103,b<=103,c<=103

对于20%的数据,a<=104,b<=104,c<=106

对于50%的数据，a<=109，b<=109,c<=109

对于100%数据，a<=3⋅1018，b<=3⋅1018,c<=3⋅1018

三个答案分值权重分别为20%,30%,50%

/*

题目大意：Ax+By=C,x>=0,y>=0,求x+y最大值，x+y最小值

x,y的解得个数

暴力算法1：枚举x,y更新O(N^2)20分

暴力算法2：枚举x，测试y是否符合情况，O(N) 40分-100分（原谅我数据太水）

很明显的扩展欧几里得

令gcd(A,B)=D;

Ax+By=C满足有解的必要条件是C mod D = 0

我们先解方程Ax+By=gcd(A,B),得到该方程一组解(p',q’)乘以C/D

即为原方程的一组解(p0,q0)

则任何(p,q)满足

p = p0 +B/D *t

q = q0–A/D *t(其中t为任意整数)都为原方程的解

我们解不等式p>=0&&q>=0得到关于t的一个区间[l,r]

(注意不等式的向下取整和向上取整)

则通解个数显然为r-l+1

最小最大解一定分别在l,r处取得（因为是线性方程）

时间复杂度O(logN)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define LL long long 

using namespace std;

LL a,b,c,x,y;

LL gcd(LL a,LL b)

{

    if(b==)return a;

    else return gcd(b,a%b);

}

LL exgcd(LL a,LL b,LL &x ,LL & y)

{

    if(b==)

    {x=;y=;return a;}

    LL r=exgcd(b,a%b,x,y);

    LL tmp=x;x=y;y=tmp-(a/b)*y;

    return r;

}

int main()

{

    freopen("BlackHawk.in","r",stdin);

    freopen("BlackHawk.out","w",stdout);

    cin>>a>>b>>c;

    LL p=gcd(a,b);

    if(c%p!=)

    {

        printf("-1 -1\n0");

        return ;

    }

    exgcd(a,b,x,y);

    LL xx=ceil((long double)-x/b*c);

    LL yy=floor((long double)y/a*c);

    LL ans=yy-xx+;

    LL ans1=x*c/p+y*c/p+(b-a)/p*yy;

    LL ans2=x*c/p+y*c/p+(b-a)/p*xx;

    if(ans<=) printf("-1 -1\n0");

    else cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<endl<<ans;

    return ;

}

巴特西

cogs 2057. [ZLXOI2015]殉国