P1511Pugna数 | |
|
问题描述
假设我们定义这样几种数:
如果一个数能表示成两个完全平方数的和(如5=4+1,10=9+1),就称这种数为helang数。
如果一个数能表示成两个完全平方数的差(如3=4-1,16=25-9),就称这种数为ylmf数。
当然可能一个数既是helang数也是ylmf数(如5=4+1=9-4)。
如果一个数既不是helang数也不是ylmf数,就称这个数是pugna数。比如6就是一个pugna数。
下面给定一个n,要你求出一个最大的n位的pugna数。
当然这个数很大,你只要求出这个数的众数和。比如189的众数和为1+8+9=18,20289的众数和为2+0+2+8+9=21
输入格式
一个整数n
输出格式
满足条件的最大的Pugna数的众数和
样例输入
1
样例输出
6
提示
0<n<=10000
n=1时,由于9=10-1,8=4+4,7=16-9,所以答案是6,众数和为6
n=2时,有99=100-1,98=49+49,97=81+16,96=100-4,95=144-49,而94什么都不是,所以答案是9+4=13