UVA1363 - Joseph's Problem(数学,迷之优化)

题意:给出n和k,1≤n,k≤1e9,计算

UVA1363 - Joseph's Problem(数学,迷之优化)

切入点是k/i 和 k/(i+1)差距不大。令pi = k/i, ri = k%i。如果pi+1 == pi,那么ri+1 == k - pi(i+1) == ri - pi

对于pi+z == pi,ri+z == ri - z*pi,这是等差数列可以O(1)计算出来。如果上界为j,那么k/j ≤ pi,j ≤ k/pi。

/*********************************************************
* --------------Tyrannosaurus--------- *
* author AbyssalFish *
**********************************************************/
#include<bits/stdc++.h>
using namespace std; typedef long long ll; ll solve(int n, int k)
{
ll ans = ;
for(int i = ; i <= n; ){
int p = k/i;
if(!p){
ans += (n+-i)*(ll)k;
break;
}
int j = min(k/p, n), r = k-i*p;
ans += (2LL*r - (j-i)*p)*(j-i+1LL)/2LL;
i = j+;
}
return ans;
} //#define LOCAL
int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
int n, k;
while(~scanf("%d%d",&n,&k)){
printf("%lld\n", solve(n,k));
}
return ;
}
上一篇:Problem J. Joseph’s Problem 约瑟夫问题--余数之和


下一篇:C语言常用知识