首页 > 代码库 > 平方数
平方数
平方数
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 3 Accepted Submission(s) : 3
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Square number is very popular in ACM/ICPC. Now here is a problem about square number again.
Let‘s consider such a kind of number called K-Omitted-Square-Number(K-OSN). N is a K-OSN if:
(1) It is a square number.
(2) Its last digit is not 0.
(3) It‘s not less than 10^K.
(4) If its last K digits are omitted, it‘s still a square number.
Now, given an even number K, you have to find the largest K-OSN.
Let‘s consider such a kind of number called K-Omitted-Square-Number(K-OSN). N is a K-OSN if:
(1) It is a square number.
(2) Its last digit is not 0.
(3) It‘s not less than 10^K.
(4) If its last K digits are omitted, it‘s still a square number.
Now, given an even number K, you have to find the largest K-OSN.
Input
There are multiple test cases in this problem.
The first line will contain a single positive integer T(T<=20) indicating the number of test cases. Each test case will be a single line containing an even number K(2<=K<=200).
The first line will contain a single positive integer T(T<=20) indicating the number of test cases. Each test case will be a single line containing an even number K(2<=K<=200).
Output
For each test case, print a single line containing the largest K-OSN. In case that it will be very large, you just need to print the number module 2009. If there are no K-OSN, or if the largest K-OSN doesn‘t exist, print "Oops!"(without quotes).
Sample Input
1 4
Sample Output
197
Author
HYNU
//数学题: 假定 m=a*10^k/2+b (a,b未知) N=m*m=a*a*10^k+b*b+2*a*b*10^k/2
那么 b*b+2*a*b*10^k/2<10^k 因为要使m最大,那么b取最小,a取越大,所以b等于1 带入不等式然后对a取整就可以求得a,b。 a<(10^k-1)/(2*10^k/2)
但是我们可以发现,当k=2时,a=4 k=4 , a=49 k=6 a=499 ......所以我们可以构造出m,然后直接求出n.
#include<stdio.h> const int MAXK=200; //最大的K const int MODNUM=2009; //用于取模的数 int main() { int tn,i; //tn为数据组数 int k,ans; //题目输入的K int digit[MAXK+10],dn; //用于存放答案的数组和数组的长度 scanf("%d",&tn); while(tn--) { scanf("%d",&k); dn=0; digit[++dn]=4; //根据规律来构造答案 for(i=1;i<k/2;i++) digit[++dn]=9; for(i=1;i<k/2;i++) digit[++dn]=0; digit[++dn]=1; // for(i=1;i<=dn;i++) //printf("%d ",digit[i]); // printf("\n"); for(ans=0,i=1;i<=dn;i++) ans=(ans*10+digit[i])%MODNUM; //printf("%d\n",ans); ans=(ans*ans)%MODNUM; printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。