 /**//*
题意:定义f(k)为k的因子个数,G(k) = f(1) + .. + f(k)
求一个k,使得G(k) = M M<=10^9
容易知道G(k) = 有因子1的数的个数 +
有因子2的数的个数 +

有因子k的数的个数
= k/1 +k/2 + k/k

求G(k) = M ,可二分
但计算G(k)用O(n)算法的话会超时
我一开始TLE
http://hi.baidu.com/aekdycoin/blog/item/16138adfd696844594ee370a.html
提到
由于整除,必然导致 [X / i]的值呈区间的形式出现
例如X = 100
X / 51 = 1
X / 52 = 1

X / 100 = 1

才回忆起有一种快速的方法计算 k/1 + k/2 + .. + k / k
next now
i 1 | 2| 3| 4| 5 6| 7 8 9 10 11 12
k/i 12 | 6| 4| 3| 2 2| 1 1 1 1 1 1
对于值为val的,其个数为now-next
O(sqrt(n))
val = k / now
next = k / (val+1) ,下一个val至少为val+1

poj 2800是求∑k%i
*/
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<cmath>

using namespace std;

*
int G(int k)
 {
int sum = 0 ;
for(int i = 1 ; i <= k ; i ++)
sum += k/i;
return sum;
}
*/

int G(int k)
  {
int sum = 0 ;
int now = k , next , val;
while(now > 0)
 {
val = k / now;
next = k / (val+1);
sum += val*(now -next);
now = next;
}
return sum;
}

int solve(int M)
  {
int low = 1 , high = 55592635;//G(55592635) > 10^9
while(low <= high)
 {
int mid = (low+high)>>1;
int g = G(mid);
if(g==M)return mid;
if(g>M)high = mid-1;
else low = mid+1;
}
return -1;
}

int main()
  {
// freopen("in","r",stdin);
int T , t = 1;
for(scanf("%d",&T) ; T-- ; )
 {
int M , ans;
scanf("%d",&M);
printf("Case %d: ",t++);
ans = solve(M);
if(ans == -1)puts("impossible!");
else printf("%d\n",ans);
}
return 0;
}

|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|