ACM数论解题报告集合.doc

Hdu 4143 y^2 = n +x^2 A Simple Problem Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1650????Accepted Submission(s): 424 Problem Description For a given positive integer n, please find the smallest positive integer x that we can find an integer y such that y^2 = n +x^2. ? Input The first line is an integer T, which is the the number of cases.Then T line followed each containing an integer n (1=n = 10^9). ? Output For each integer n, please print output the x in a single line, if x does not exit , print -1 instead. #includestdio.h#includemath.hint main(){??? int i,t,n,x,flag;??? scanf(%d,t);??? while(t--)??? {??? ??? flag=0;??? ??? scanf(%d,n); ??? ??? i=sqrt(n);//n的平方根??? ??? for(i;i=1;i--)??? ??? {??? ??? ??? if(n%i==0(n/i-i)%2==0n/i!=i)??? ??? ??? {??? ??? ??? ??? x=(n/i-i)/2;??? ??? ??? ??? printf(%d\n,x);??????????????? flag=1;??? ??? ??? ??? break;??? ??? ??? }??? ??? ??? ??? ??? }??? ??? if(flag==0) printf(-1\n);??? }??? return 0;}/*一开时超时 是百分百的事?? 不过要敢于写出超时的? （在时间还充裕的情况下）后来一直不知道真么做。? 对于这种类型的题目要密切结合式子的特点 把2层循环变成一层n=（x+y）*(x-y)? 让i=x-y n/i做x+y??? x=(n/i-i)/2;然后找出各种条件限制 满足则可求出结果由于程序有可能出现n/i=i的情况 但是题目中题意告诉我们不可能所以千万要排除这种情况后来在这个地方也错了几次*/ 另外此题也可用欧几里得去做 hdu数论之Leftmost Digit 题目大意是输入N，求N^N的最高位数字。1=N=1,000,000,000估计大家看到N的范围就没想法了。确实N的数字太大，如果想算出结果，即使不溢出也会超时。这题我纠结了很久。在同学的提示下ac了。题目是这样转化的。首先用科学计数法来表示 N^N = a*10^x; 比如N = 3; 3^3 = 2.7 * 10^1;我们要求的最右边的数字就是(int)a，即a的整数部分;OK, 然后两边同时取以10为底的对数 lg(N^N) = lg(a*10^x) ;化简 N*lg(N) = lg(a) + x;继续化 N*lg(N) - x = lg(a)a = 10^(N*lg(N) - x);现在就只有x是未知的了，如果能用n来表示x的话，这题就解出来了。又因为，x是N^N的位数。比如 N^N = 1200 == x = 3; 实际上就是 x 就是 lg(N^N) 向下取整数，表示为[lg(N^N)]ok a = 10^(N*lg(N) - [lg(N^N)]); 然后(int)a 就是答案了。#includestdio.h#includemath.hint main(){?int t;?long long ans;?double k,n;?scanf(%d,t);?while(t--)?{???scanf(%lf,n);??k=n*log10(n);??k=k-(long long)k;??????? ans=(long long)pow(10.0,k);??printf(%lld\n,ans);?}?return 0;}注意 最好让log