CodeForces 755D PolandBall and Polygon —

CodeForces 755D PolandBall and Polygon ——（xjbg）

　　每次连线，起点和终点之间，每一个被点亮的点，这些点都能连出去两条线，因此可以增加的块数+2（1这个点除外，因为只有连出的点没有连进的点），计算起点和终点之间有几个点被点亮即可，然后1这个点特判一下。感觉，可以用线段树维护。。不过这题还是有规律的，每转过一圈，两线之间的点数就会加1，然后O(n)扫一遍就行了。注意答案会爆int。

　　代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e6 + 5;
 4 typedef long long ll;
 5 
 6 int n,k;
 7 
 8 int main()
 9 {
10     cin >> n >> k;
11     k = min(k,n-k);
12     int add = 1;
13     int pos = 1;
14     ll have = 1;
15     for(int i=1;i<=n;i++)
16     {
17         if(pos + k > n + 1)
18         {
19             add++;
20             have += add;
21             add++;
22         }
23         else have += add;
24         pos += k;
25         if(pos > n) pos -= n;
26         cout << have << " ";
27     }
28     puts("");
29     return 0;
30 }