http://codeforces.com/contest/755/problem/D
// 我也觉得非平面图不能用欧拉公式，但是也能过，不知道为什么。求大佬留言。
这题其实就是平面图，因为它有很多个交点。中途的交点使得图的阶数变大了
所以我的思路就是求出V、E、然后解出F。V - E + F = 2
其中每连接一条边，增加的交点就是其路径上的点被多少次经过。（不包括自己端点）
这个可以用BIT维护下。
然后当k > n - k的时候，需要反向一下，因为这样其实就相当于镜面对称一下而已，不然会wa的。
比如5 3 的时候，会翻车
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e6 + ;
LL c[maxn];
int n, k;
int lowbit(int x) {
return x & (-x);
}
void add(int pos, int val) {
while (pos <= n) {
c[pos] += val;
pos += lowbit(pos);
}
}
LL query(int pos) {
LL ans = ;
while (pos > ) {
ans += c[pos];
pos -= lowbit(pos);
}
return ans;
}
void work() {
scanf("%d%d", &n, &k);
int be = ;
LL e = n;
LL v = n;
k = min(k, n - k); //这个是必须的，试试5 3 就知道
for (int i = ; i <= n; ++i) {
int from = be;
int to = be + k;
if (to > n) {
to -= n;
LL addv = query(to - );
if (from != n) {
addv += query(n) - query(from);
}
e += addv;
e += addv + ;
v += addv;
printf("%I64d ", - v + e - );
add(from, );
add(to, );
be = to;
} else {
LL addv = query(to - ) - query(from);
e += addv;
e += addv + ;
v += addv;
printf("%I64d ", - v + e - );
add(from, );
add(to, );
be = to;
}
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}