Codeforces 382 B. Number Busters（數論推公式）

B. Number Busters time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Arthur and Alexander are number busters. Today they've got a competition.

Arthur took a group of four integers a, b, w, x (0 ≤ b < w, 0 < x < w) and Alexander took integer с. Arthur and Alexander use distinct approaches to number bustings. Alexander is just a regular guy. Each second, he subtracts one from his number. In other words, he performs the assignment: c = c - 1. Arthur is a sophisticated guy. Each second Arthur performs a complex operation, described as follows: if b ≥ x, perform the assignment b = b - x, if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b).

You've got numbers a, b, w, x, c. Determine when Alexander gets ahead of Arthur if both guys start performing the operations at the same time. Assume that Alexander got ahead of Arthur if c ≤ a.

Input

The first line contains integers a, b, w, x, c (1 ≤ a ≤ 2·109, 1 ≤ w ≤ 1000, 0 ≤ b < w, 0 < x < w, 1 ≤ c ≤ 2·109).

Output

Print a single integer — the minimum time in seconds Alexander needs to get ahead of Arthur. You can prove that the described situation always occurs within the problem's limits.

Sample test(s) input

4 2 3 1 6
      

output

2
      

input

4 2 3 1 7
      

output

4
      

input

1 2 3 2 6
      

output

13
      

input

1 1 2 1 1
      

output

題意：有五個數a,b,w,x和c，每一秒中：c會減少一個，但是a有兩種選擇，當b>=x時，a不變，b=b-x;當b<x時，a減少一個，并且b=w-(x-b),問幾秒後a=c？ 題解： 這裡可以看出如果是b>=X時，a與c之間的內插補點才會減小，否則隻會B增加但是a與c之間的內插補點不會減小，這裡将b=w-(x-b)可以變為b=b+(w-x);即每一次B要加時都是加上（w-x），這樣我們可以設a減少了M次，其中b<x時有n次，這樣b>=x時有m-n次，即a減少了n次，那麼因為最後a=b是以 c-m=a-n 即 m-n=c-a 因為每一次 b>=x 吧b都會減少一個x，一共減了m-n次，又因為本身b是有一定的初始值的，本身的初始值可以減 b/x 次 x那麼剩下的（m-n）-b/x 次減少的b的值就要由加的n次（w-x）來提供了，又因為本身b在減少完 b/x 次X後還會剩下 b%x 的值，是以由N次（w-x）提供的就是值就是 （（m-n）-b/x）*x-b%x，是以 （（m-n）-b/x）*x-b%x=（w-x）*n。又因為前面求出（m-n）=（c-a）是以（（c-a）-b/x）*x-b%x=（w-x）*n。這裡還要注意一點：要是（（c-a）-b/x）*x-b%x能整除（w-x）那麼直接就能求出n，要是不能整除的話求出的 n 還要加 1 ，原因很簡單能多不能少呀，要求的是 m 這裡已經求出n來了，那麼由 m-n=c-a 可得m=n+c-a，即答案。 題目連結：http://codeforces.com/problemset/problem/382/B 代碼：

#include<iostream>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;

int main(){
    LL a,b,w,x,c;
    scanf("%lld%lld%lld%lld%lld",&a,&b,&w,&x,&c);
    if(c<=a) printf("0\n");
    else {
        LL p1=(c-a-b/x)*x-b%x;
        LL p2=w-x;
        LL p;
        if(p1%p2==0) p=p1/p2;
        else p=p1/p2+1;
        printf("%lld\n",p+c-a);
    }
    return 0;
}
要是還有哪裡不明白歡迎提出來，歡迎各位大神們提出錯誤