首页 > 代码库 > hdoj 2601(判断N=i*j+i+j)
hdoj 2601(判断N=i*j+i+j)
Problem E
Time Limit : 6000/3000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 16 Accepted Submission(s) : 9
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
When Teddy was a child , he was always thinking about some simple math problems ,such as “What it’s 1 cup of water plus 1 pile of dough ..” , “100 yuan buy 100 pig” .etc..
One day Teddy met a old man in his dream , in that dream the man whose name was“RuLai” gave Teddy a problem :
Given an N , can you calculate how many ways to write N as i * j + i + j (0 < i <= j) ?
Teddy found the answer when N was less than 10…but if N get bigger , he found it was too difficult for him to solve.
Well , you clever ACMers ,could you help little Teddy to solve this problem and let him have a good dream ?
One day Teddy met a old man in his dream , in that dream the man whose name was“RuLai” gave Teddy a problem :
Given an N , can you calculate how many ways to write N as i * j + i + j (0 < i <= j) ?
Teddy found the answer when N was less than 10…but if N get bigger , he found it was too difficult for him to solve.
Well , you clever ACMers ,could you help little Teddy to solve this problem and let him have a good dream ?
Input
The first line contain a T(T <= 2000) . followed by T lines ,each line contain an integer N (0<=N <= 1010).
Output
For each case, output the number of ways in one line.
Sample Input
213
Sample Output
01
易知用两个循环嵌套判断n=i*j+i+j必然超时,可以推得n+1=i*j+i+j+1,即为n+1=(i+1)*(j+1);
题中提示j>=i>0;那么j+1>=i+1,用x代替(i+1),将x从2遍历到sqrt(n+1),在此条件下判断(n+1)%x,若为0,说明
存在(j+1),使得(i+1)*(j+1)=n+1,由于是在(i+1)<=sqrt(n+1)的条件下的结果,必然有(j+1)>=(i+1)成立。
时间复杂度由O(n)变为O(sqrt(n)).
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。