每次连线，起点和终点之间，每一个被点亮的点，这些点都能连出去两条线，因此可以增加的块数+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 }
CodeForces 755D PolandBall and Polygon ——（xjbg）
原文：http://www.cnblogs.com/zzyDS/p/6291752.html