hdu1597的两种解法

xiaoxiao2021-03-01  4

好吧,虽然是个水题,可以有个技巧。 有些题 可以直接用数学公式解决的、、、这里鼓励一下自己、、、、在几次WA后,忍了忍 一直没看解题报告

法一:

打表,记录1-65535的和(开始没有注意到,计算到100000000,sum还是不够2^31,后来算算前n项和才用计算到65535而已)。

由此也发现一个问题,数字的存储是一个循环,先是正数,然后超出正数范围后变成负数,再超出负数范围变成正数。

#include <iostream> using namespace std; int sum[65536]; int main() { int k; cin>>k; int i;sum[0]=0; for(i=1;i<65536;i++) sum[i]=sum[i-1]+i; while(k--) { int m;cin>>m; for(i=1;i<65536;i++) if(m<=sum[i]) break; m-=sum[i-1]; m%=9; if(m==0) cout<<"9"<<endl; else cout<<m<<endl; } return 0; }法二:

转变为解一元二次方程,因为前n项的和m=n*(n+1)/2.于是,n=sqrt(2m+0.25)-0.5【ceil是向上取整函数】

代码:

#include <iostream> #include <math.h> using namespace std; int main() { unsigned long n; int k; while(cin>>k) { while(k--) { cin>>n; double i=ceil(sqrt(2*n*1.0+0.25)-0.5); //ceil()函数为向上取整 unsigned long j=(unsigned long)i-1; n=n-j*(j+1)/2; if(n%9)cout<<n%9<<endl; else cout<<9<<endl; } } return 0; }

转载请注明原文地址: https://www.6miu.com/read-3650309.html

最新回复(0)