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%

【來源】

這個題就是個擴展歐幾裡得的裸題，也不算太裸，因為涉及到求最小值和最大值的問題

但是自己寫了一個交上去爆零，後來看了看比人寫的代碼，發現還是懵逼在45—49行里。。

4546貌似是求最大區間，，但是為什麼要/b/a呢？x為什麼要加負號呢？？

還有ans1，ans2的b-a是什麼鬼。。

啊啊啊啊啊啊為什麼為什麼為什麼。。。。。。

=.=

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<vector>
 6 #include<map>
 7 #define LL long long 
 8 using namespace std;
 9 LL a,b,c,x,y;
10 LL read(LL & n)
11 {
12     int flag=0,x=0;char c='/';
13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
14     while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();
15     if(flag)n=-x;
16     else n=x;
17 }
18 LL gcd(LL a,LL b)
19 {
20     if(b==0)return a;
21     else return gcd(b,a%b);
22 }
23 LL exgcd(LL a,LL b,LL &x ,LL & y)
24 {
25     if(b==0)
26     {x=1;y=0;return a;}
27     LL r=exgcd(b,a%b,x,y);
28     LL tmp=x;x=y;y=tmp-(a/b)*y;
29     return r;
30 }
31 int main()
32 {
33     //freopen("BlackHawk.in","r",stdin);
34     //freopen("BlackHawk.out","w",stdout);
35     //read(a);read(b);read(c);
36     cin>>a>>b>>c;
37     LL p=gcd(a,b);
38     if(c%p!=0)
39     {
40         printf("-1 -1\n0");
41         return 0;
42     }
43     exgcd(a,b,x,y);
44 //    printf("%d %d",x,y);
45     LL xx=ceil((long double)-x/b*c);
46     LL yy=floor((long double)y/a*c);
47     LL ans=yy-xx+1;
48     LL ans1=x*c/p+y*c/p+(b-a)/p*yy;
49     LL ans2=x*c/p+y*c/p+(b-a)/p*xx;
50     if(ans<=0) printf("-1 -1\n0");
51     else cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<endl<<ans;
52     return 0;
53 }