消減整數（數論）

鏈接：https://ac.nowcoder.com/acm/contest/10746/F
來源：牛客網

題目描述
給你一個數字N依序減掉1,2,3,…直到不夠減，如果剛好減到0就結束，否則就加上N繼續從1開始減，直到減到0為止，
請給出一個數字，計算對于該數字一共重復了幾次這個程序，

輸入描述
輸入的第一行有一個正整數 t t t， 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104，代表測驗資料的組數
接下來t行每行一個數 N N N， 1 ≤ N ≤ 1 0 8 1 \le N \le 10^8 1≤N≤108

輸出描述
對于每組輸入，若能夠在有限次內削減為0，在一行中輸出重復的程序次數，否則輸出 “Impossible”，

樣例輸入
3
1
2
3

樣例輸出
1
2
1

解題思路
BF做法，模擬每次依序減掉1,2,3,…直到不夠減，記錄次數，優化的方法是把前綴后記錄，用二分查找直接完成一次程序，但這樣還是會超時，
有一個討巧的方法，存盤已經得到答案的值，可以AC，測驗資料有很多重復的值，
注意：不能在回圈中使用已經存盤的值，因為每一次重新加上的數 x x x的值不同，

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int T, n;
const int N = 1e5;
int a[N], cnt;
void init() {
	int i = 1, sum = 0;
	while (sum < 1e8) {
		sum += i;
		a[i] = sum;
		i++;
	}
	cnt = i;
}
map<int, int> mp;
void solve(int x) {
	if (mp.count(x)) {
		printf("%d\n", mp[x]);
		return;
	}
	int t = x, res = 0;
	while (1) {
		res++;
		int i = lower_bound(a+1, a+cnt, t) - a;
		if (t == a[i]) {
			mp[x] = res;
			printf("%d\n", res);
			break;
		}
		t -= a[i-1];
		t += x;
	}
}
int main() {
	//freopen("消減整數.in", "r", stdin);
	scanf("%d", &T);
	init();
	while (T--) {
		scanf("%d", &n);
		solve(n);
	}
	return 0;
}

正解，假設 N N N不夠減后余數是 t t t，下一個要減的數是 i i i， t ＜ i t＜i t＜i不斷加上 N N N后重復，余數為 2 t 2t 2t, 3 t 3t 3t,… a t at at，當 a t ＞ i at＞i at＞i時，減去 i i i后的余數 a t ? i at-i at?i又是小于 i i i的，再次重復的余數為 ( a + 1 ) t ? i (a+1)t-i (a+1)t?i，直到 b t ? i ＞ i bt-i＞i bt?i＞i，余數變為 b t ? 2 i bt-2i bt?2i，重復下去，直到 c t ? d i = i ct-di=i ct?di=i，即 c t = l c m ( t , i ) ct=lcm(t,i) ct=lcm(t,i)，此時的 c c c即是重復程序的次數，

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int T, n;
const int N = 1e5;
int a[N], cnt;
void init() {
	int i = 1, sum = 0;
	while (sum < 1e8) {
		sum += i;
		a[i] = sum;
		i++;
	}
	cnt = i;
}
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
void solve(int x) {
	int i = lower_bound(a+1, a+cnt, x) - a;
	int t = x - a[i-1];
	int res = i * t / gcd(i, t);
	printf("%d\n", res/t);
}
int main() {
	//freopen("消減整數.in", "r", stdin);
	scanf("%d", &T);
	init();
	while (T--) {
		scanf("%d", &n);
		solve(n);
	}
	return 0;
}