zoj 3175 Number of Containers (大数灵活题，除2改成平方根)

For two integers?m?and?k,?k?is said to be a container of?m?if?k?is divisible by?m. Given 2 positive integers?n?and?m?(m?<?n),the function f(n,?m) is defined to be the number of containers of?m?which are also no greater than?n. For example,f(5,1)=4,f(8,2)=3,f(7,3)=1,4)=0...

Let us define another function F(n) by the following equation:?

Input

There are multiple test cases. The first line of input contains an integer?T(T<=200) indicating the number of test cases. Then?Ttest cases follow.

Each test case contains a positive integer?n?(0 <?n?<= 2000000000) in a single line.

Output

For each test case,output the result F(n) in a single line.

Sample Input

2
1
4

Sample Output

0

4

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3216

本质就是求(n/1+n/2+...+n/n-1)-n的值

数字太大，不能用n/2,只能用平方根（这个在比赛的时候完全想不到。。）

推导过程：比如 n=10

=1*10

=2*5

=3*3

10-5=5,5-3=2

然后我们又惊奇地发现最后的结果10,5,3,2,1,1

1有5个，2有2个，于是找到规律。

但是对于像8这样的数字来说，还有两个数字没有赋值到，于是sum+=未赋值个数*当前的b

其他方法：http://www.voidcn.com/article/p-wexwrcki-bew.html

int main(){
	int t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		ll s=0;
		ll a=n,b=1,c=1;
		for(ll i=2;i*i<=n;++i){
			s+=n/i+(a-n/i)*b;
			c+=a-(n/i)+1;
			b++;
			a=n/i;
		}
		s+=(n-c)*b;
		cout<<s<<endl;
	}
	return 0;
}