ACM数论解题报告集合.docx
- 文档编号:9242393
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:46
- 大小:116.13KB
ACM数论解题报告集合.docx
《ACM数论解题报告集合.docx》由会员分享,可在线阅读,更多相关《ACM数论解题报告集合.docx(46页珍藏版)》请在冰点文库上搜索。
ACM数论解题报告集合
Hdu4143y^2=n+x^2
ASimpleProblem
TimeLimit:
2000/1000MS(Java/Others) MemoryLimit:
65535/32768K(Java/Others)
TotalSubmission(s):
1650 AcceptedSubmission(s):
424
ProblemDescription
Foragivenpositiveintegern,pleasefindthesmallestpositiveintegerxthatwecanfindanintegerysuchthaty^2=n+x^2.
Input
ThefirstlineisanintegerT,whichisthethenumberofcases.
ThenTlinefollowedeachcontaininganintegern(1<=n<=10^9).
Output
Foreachintegern,pleaseprintoutputthexinasingleline,ifxdoesnotexit,print-1instead.
#include
#include
intmain()
{
inti,t,n,x,flag;
scanf("%d",&t);
while(t--)
{
flag=0;
scanf("%d",&n);
i=sqrt(n);
for(i;i>=1;i--)
{
if(n%i==0&&(n/i-i)%2==0&&n/i!
=i)
{
x=(n/i-i)/2;
printf("%d\n",x);
flag=1;
break;
}
}
if(flag==0)printf("-1\n");
}
return0;
}
/*一开时超时是百分百的事 不过要敢于写出超时的 (在时间还充裕的情况下)
后来一直不知道真么做。
对于这种类型的题目要密切结合式子的特点把2层循环变成一层
n=(x+y)*(x-y) 让i=x-yn/i做x+y x=(n/i-i)/2;
然后找出各种条件限制满足则可求出结果
由于程序有可能出现n/i=i的情况但是题目中题意告诉我们不可能所以千万要排除这种情况
后来在这个地方也错了几次
*/
另外此题也可用欧几里得去做
hdu数论之LeftmostDigit
题目大意是输入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)]
oka=10^(N*lg(N)-[lg(N^N)]);然后(int)a就是答案了。
#include
#include
intmain()
{
intt;
longlongans;
doublek,n;
scanf("%d",&t);
while(t--)
{
scanf("%lf",&n);
k=n*log10(n);
k=k-(longlong)k;
ans=(longlong)pow(10.0,k);
printf("%lld\n",ans);
}
return0;
}
注意最好让log中的数都是double型
另外遇到n的n次方这种类型 要第一时间考虑到log
另外t绝对不能为longlong这样会超时
所以以后对于决定case的数要用int输入
最小差值
给出一个整数数组a1,a2,…,an,求数组中两个数的最小差值。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ACM 数论 解题 报告 集合