HNUST--模的和

2019-04-13 12:15发布

站内文章 / 模拟电子
13332 0 1007
     这是14年湖南科技大学校赛水题~~幸好之前做过类似的题目，发现会TLE后，就立马找规律                                                                             模的和 分析：1.看到n的取值和测试数据的数目，一看就知道普通模拟是会TLE的；            2.一般来说，和求模有关的题目，一般都是很有规律性的，这不，果断打表试了下，果然不出所料           3.由下表的数据可以发现，后面由一系列的等差数列组成，前面的不怎么明显，把主要的等差数列的区间写出来，发现起点和  n/(i+1)+1  相等，而且大概当起点为SQRT(N)左右的时候，等差并不是很明显了，不过这个时候剩下的数据很少了，直接模拟相加就行！ 代码 #include #include #include #define N 1000000007 typedef long long ll; using namespace std; ll sum; int main() { ll n,i,st,ed,cnt; while(scanf("%I64d",&n)!=EOF){ if(n<=0) break; sum=0;ed=n+1; for(i=1;i<=sqrt(n);i++){ if(n/i>sqrt(n)){ //大于 SQRT（N）的数列比较长，求起来方便不会出错 st=n/(i+1)+1; //等差数列的起点 cnt=ed-st; //数列中的元素个数 // printf("st==%I64d ed==%I64d cnt == %I64d ",st,ed,cnt); sum+=cnt*(n%st+n%(ed-1))/2; //等差数列求和 ed=st; //更新等差数列的末端 } sum+=n%i; //无规律的前面几项的和 } printf("%I64d ",sum%N); } return 0; }