codeforces #332 div 2 D. Spongebob and Squares

2015年12月23日 0 作者 CrazyKK

http://codeforces.com/contest/599/problem/D
题意:给出总的方格数x,问有多少种不同尺寸的矩形满足题意,输出方案数和长宽(3,5和5,3算两种)
思路:比赛的时候gg了。。其实稍微在纸上推一下。就会得到对于n,m的矩形,一共会有-n*n*n+3*n*n*m+n+3*n*m的方格。数量级是n3。
我们可以实际跑一遍。发现对于x1E18的数量级,n不会超过1442550,1E6,可以搞。

需要注意的是,一个是会爆int,所以记得用long long

另一个是如果两个数相等,记得只输入一组,并且方案数-1

我是用set +pair存的答案。。反向遍历set的时候要用reserve_iterator…