time limit per test4 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
PolandBall has such a convex polygon with n veritces that no three of its diagonals intersect at the same point. PolandBall decided to improve it and draw some red segments.
He chose a number k such that gcd(n, k) = 1. Vertices of the polygon are numbered from 1 to n in a clockwise way. PolandBall repeats the following process n times, starting from the vertex 1:
Assume you’ve ended last operation in vertex x (consider x = 1 if it is the first operation). Draw a new segment from vertex x to k-th next vertex in clockwise direction. This is a vertex x + k or x + k - n depending on which of these is a valid index of polygon’s vertex.
Your task is to calculate number of polygon’s sections after each drawing. A section is a clear area inside the polygon bounded with drawn diagonals or the polygon’s sides.
Input
There are only two numbers in the input: n and k (5 ≤ n ≤ 106, 2 ≤ k ≤ n - 2, gcd(n, k) = 1).
Output
You should print n values separated by spaces. The i-th value should represent number of polygon’s sections after drawing first i lines.
Examples
input
5 2
output
2 3 5 8 11
input
10 3
output
2 3 4 6 9 12 16 21 26 31
Note
The greatest common divisor (gcd) of two integers a and b is the largest positive integer that divides both a and b without a remainder.
For the first sample testcase, you should output “2 3 5 8 11”. Pictures below correspond to situations after drawing lines.
【题目链接】:http://codeforces.com/contest/755/problem/D
【题解】
两个点之间如果连一条线;
则如果这条线没有穿过其他线;
则平面+1
否则平面+=1+穿过的线条数;
假设当前是第now个点;
则看一下now+1..now+k-1这个范围内的点连的线的条数;即为这条线穿过的其他线的次数;
但是如果k>n/2了,那么可能连线的时候,now+1..now+k-1这些点有出边,但是不会和这条线相交.
比如
5 3
可以看到这里的第二条线.
虽然5 1 中1号点有出边,但是不会和新连的第二条线有交点;
这种情况下可以让n=n-k;
这时k< n/2
且答案是不会变的;
如上图可以把图左右倒过来.
LL以及上面这个是HACK点
写个线段树维护;
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int MAXN = 1e6+100;
int n,k;
LL sum[MAXN<<2];
LL query(int L,int R,int l,int r,int rt)
{
if (L>R)
return 0;
if (L <= l && r<=R)
return sum[rt];
int m = (l+r)>>1;
LL temp1=0,temp2=0;
if (L<=m)
temp1 = query(L,R,lson);
if (m < R)
temp2 = query(L,R,rson);
return temp1+temp2;
}
void up_data(int pos,int l,int r,int rt)
{
if (l==r)
{
sum[rt]++;
return;
}
int m = (l+r)>>1;
if (pos<=m)
up_data(pos,lson);
else
up_data(pos,rson);
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
rei(n);rei(k);
k = min(k,n-k);
int now = 1;
LL ans = 1;
rep1(i,1,n)
{
int nex = now+k;
LL temp;
if (nex>n)
temp = query(now+1,n,1,n,1)+query(1,nex-n-1,1,n,1);
else
temp = query(now+1,nex-1,1,n,1);
ans += temp+1;
cout << ans;
if (i==n)
puts("");
else
putchar(' ');
up_data(now,1,n,1);
if (nex>n)
nex-=n;
up_data(nex,1,n,1);
now = nex;
}
return 0;
}