# [2018 Blue Bridge Cup final] d-joseph ring

2020-11-10 17:23:40 Fool_one

Look at the data range first ,n, k <= 1e6, If you use a queue to solve problems , Time complexity can reach \$O(n * k)\$ It's bound to be overtime .

obviously , This problem should be solved mathematically , You can use \$O(n)\$ To solve the time complexity of , How to solve it ?

Let's first look at the schematic diagram ：

It's actually a recursive relationship ,f[i] Express i personal , from 1 Start counting , The number of the last loser , When the number is k The person whose number is k - 1 When you're out of the team , There's only one left i - 1 personal , and f[i - 1] Express i - 1 personal ,k from 1 Start counting , Finally, the number of the person left , Obviously from 1 The one who started counting , The number is not 0 , And become k, But in the recursion time needs to record the original number, needs to add k, Then the mathematical recurrence formula is ：

f[i] = (f[i - 1] + k) % n.

```#include <iostream>
using namespace std;

int n, m, ans = 0;

//  Mathematical methods
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
ans = (ans + m) % i;
}
cout << ans + 1 << endl;
return 0;
}```