Mashmokh and Tokens（数学）

B. Mashmokh and Tokens

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Bimokh is Mashmokh's boss. For the following n days he decided to pay to his workers in a new way. At the beginning of each day he will give each worker a certain amount of tokens. Then at the end of each day each worker can give some of his tokens back to get a certain amount of money. The worker can save the rest of tokens but he can't use it in any other day to get more money. If a worker gives backw tokens then he'll get  dollars.

Mashmokh likes the tokens however he likes money more. That's why he wants to save as many tokens as possible so that the amount of money he gets is maximal possible each day. He has n numbers x1, x2, ..., xn. Number xi is the number of tokens given to each worker on the i-th day. Help him calculate for each of n days the number of tokens he can save.

Input

The first line of input contains three space-separated integers n, a, b (1 ≤ n ≤ 105; 1 ≤ a, b ≤ 109). The second line of input containsn space-separated integers x1, x2, ..., xn (1 ≤ xi ≤ 109).

Output

Output n space-separated integers. The i-th of them is the number of tokens Mashmokh can save on the i-th day.

Sample test(s)

input

5 1 4
12 6 11 9 1

output

0 2 3 1 1 

input

3 1 2
1 2 3

output

1 0 1 

input

1 1 1
1

output

0 

 

       题意：

       给出 N（1 ~ 10 ^ 5），A（1 ~ 10 ^ 9），B（1 ~ 10 ^ 9），后给出这 N 个数（1 ~ 10 ^ 9），代表每天拥有的代币个数，每天都可以向雇主兑换钱币，兑换的规则是给 w 给雇主就可以换取 w * （a / b）（向下取整）这么多的钱币，问每天给代币从而每天都能获取最大的钱币数，输出能剩下的最大代币数。

  

       思路：

       数学。一开始单纯的想只要取模就好了，可是举例后发现不是这样的：

       比如：a = 2，b = 3 。若 ai = 7 的话，( 7 X 2 ) % 3 = 2，取模的话是剩下两个，但是 （ 7 X 2 ）/ 3 = 4.67 = 4，而 （6 X 2）/  3 = 4，说明 7 个可以获得 4 个钱币，6 个也可以获得 4 个钱币，那么用 6 个，最大剩余代币量就是 1 而不是 2 。所以正确解法应该是：

       先算出 （ ai * a ）/ b 向下取整的可获得的最大兑换钱币数 k ，再返回去用这个 最大兑换钱币数k 算出 最少代币用量 ，总量 ai - 最少代币用量 剩下的自然就是 所剩的最大代币数了。

       比如：a = 3，b = 4 。若 ai = 7，可得最大兑换钱币数是 5，而 （5 X 4 ）/ 3 = 6，且不能整除，说明 6 个钱币是不能换到 5 个钱币的，只能换到 4 个，所以应该 6 要 + 1 = 7 才对。

       返回去算出最少代币用量要判断 （k * b） 能不能整除 a，若能整除，说明这个数刚刚好为最少代币用量，若不能，则这个最少代币用量应该在除数的基础上 + 1。

 

       AC：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;

ll res[100005];

int main () {
        int n, a, b;
        scanf("%d%d%d", &n, &a, &b);

        for (int i = 1; i <= n; ++i) {
                ll ans, t;
                scanf("%I64d", &ans);
                t = ((ll)ans * a) / (ll)b;
                res[i] = ans - (t * b) / (ll)a;
                if((t * b) % (ll)a) res[i]--;
        }

        printf("%I64d", res[1]);
        for (int i = 2; i <= n; ++i)
                printf(" %I64d", res[i]);
        printf("\n");

        return 0;
}