Subtractive integer (number theory)

link ：https://ac.nowcoder.com/acm/contest/10746/F
source ： Cattle from

Title Description
Here's a number N Subtract sequentially 1,2,3,… Until it's not enough . If it happens to be reduced to 0 ends , Otherwise, add N Continue from 1 Begin to reduce , Until it's reduced to 0 until .
Please give me a number , The calculation repeats the process several times for this number .

Input description
The first line of input has a positive integer $t$,$1\le t\le 10^4$, Represents the number of groups of test data
Next t One number per line $N$,$1\le N\le 10^8$

Output description
For each group of input , If it can be reduced to 0, Output the number of times the process is repeated in one line , Otherwise output “Impossible”.

The sample input
3
1
2
3

Sample output
1
2
1

Their thinking
BF practice , Simulate subtracting each time 1,2,3,… Until it's not enough , Record times , The optimization method is to record the prefix , Use binary search to complete a process directly , But it will still time out .
There's a trick , Store the values that have been answered , Sure AC, The test data has many duplicate values .
Be careful ： You cannot use a stored value in a loop , Because the number added each time $x$ The value is different. .

#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(" Subtract an integer .in", "r", stdin);
	scanf("%d", &T);
	init();
	while (T--) {
    
		scanf("%d", &n);
		solve(n);
	}
	return 0;
}

Positive solution , hypothesis $N$ Not enough minus the remainder is $t$, The next number to subtract is $i$,$t＜i$ Keep adding $N$ Repeat after , Remainder is $2t$,$3t$,…$at$, When $at＞i$ when , subtract $i$ Remainder after $at-i$ Less than... Again $i$ Of , The remainder of the repetition is $(a+1)t-i$, until $bt-i＞i$, The remainder becomes $bt-2i$, Repeat , until $ct-di=i$, namely $ct=lcm(t,i)$, At this time $c$ Is the number of times the process is repeated .

#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(" Subtract an integer .in", "r", stdin);
	scanf("%d", &T);
	init();
	while (T--) {
    
		scanf("%d", &n);
		solve(n);
	}
	return 0;
}