Kolya is developing an economy simulator game. His most favourite part of the development process is in-game testing. Once he was entertained by the testing so much, that he found out his game-coin score become equal to 0.
Kolya remembers that at the beginning of the game his game-coin score was equal to n and that he have bought only some houses (for 1 234 567 game-coins each), cars (for 123 456 game-coins each) and computers (for 1 234 game-coins each).
Kolya is now interested, whether he could have spent all of his initial n game-coins buying only houses, cars and computers or there is a bug in the game. Formally, is there a triple of non-negative integers a, b and c such that a × 1 234 567 + b × 123 456 + c × 1 234 = n?
Please help Kolya answer this question.
题目大意：a物品价格1234567 b物品价格123456 c价格 1234 问 n元钱随意组合三种物品是否正好能全部花完
解题思路：这题用三个for循环，简单粗暴省事，但是一定超时，所以要优化为2个for循环。那就一个for循环控制a物品的数量，一个for循环控制b物品的数量，剩下的都卖c物品就行了
#include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <iostream> #include <cstring> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <list> #define LL long long #define INF 0x3f3f3f3f #define mem(a, b) memset(a, b, sizeof(a)) #define PI 3.1415926 using namespace std; const int N = 199999; int main() { int n; while(scanf("%d", &n)!= EOF) { int t = 0; if(n % 1234567 == 0 || n % 123456 == 0 || n % 1234 == 0) { cout << "YES" << endl; break; } for(int i = 0; i < 100; i++) { int q = n - 1234567 * i; if(q > 0) //这里一定要判断q是否大于0，否则负数也能可能除尽 { for(int j = 0; j < 1000; j++) { int w = q - 123456 * j; if(w >= 0) { if(w == 0 || w % 1234 == 0) { cout << "YES" << endl; t = 1; break; } } } } if(t) break; } if(t == 0) cout << "NO" << endl; } return 0; }