2058(等差求和)

el/2024/3/2 11:38:35

HDU 2058 The sum problem

等差求和公式:

Sn=(a1+aN)*n/2
    =(a1+a1+d(n-1))*n/2
    =a1*n+d(n-1)*n/2;
因为此处公差d=1,所以Sn=a1*n+(n-1)*n/2,当从第一项开始算起时(因本题首项为1,即a1=1时),Sn=M时的项的个数n最多;
a1=1,现在又可化简为Sn=n+(n-1)*n/2=(n+1)n/2;
由题意得M=Sn,N为项的个数,则N<=n(max)=sqrt(Sn*2)=sqrt(M*2);
因此原式M=Sn =a1*n+(n-1)n/2=a1*N+(N-1)N/2,可得a1*N=M-(N-1)N/2;
数据都已经全了,现在只要遍历n(max)以内项数中,Sn=M的个数即可。
那么如何判断Sn=M呢?也就是判断a1*N=Sn-(N-1)N/2;得到的a1*N这个数能否被N整除,因为整除的话,说明首项存在于序列


  1. #include<stdio.h>
  2. #include<math.h>
  3. int main(){
  4. int N,M;
  5. while(scanf("%d%d",&N,&M),N||M){
  6. int len = (int)sqrt(M*2.0);
  7. int a1_len=0;//首项a1与len的乘积
  8. for (;len>0;len--){
  9. a1_len=M-(len-1)*len/2;//a1*N=M-(N+1)N/2;
  10. if(a1_len%len==0){
  11. printf("[%d,%d]\n",a1_len/len,a1_len/len+len-1);
  12. }
  13. }
  14. puts("");
  15. }
  16. return 0;
  17. }



http://www.ngui.cc/el/4466238.html

相关文章

HDU 2059(dp)

龟兔赛跑 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description 据说在很久很久以前&#xff0c;可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后&#xff0c;心中郁闷&#xff0c;发誓要报仇雪恨&#xff0c;于是…

匈牙利算法 (二分匹配法)

过山车 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10683 Accepted Submission(s): 4699 Problem Description RPG girls今天和大家一起去游乐场玩&#xff0c;终于可以坐上梦寐以求的过山车了。可是&am…

HDU 汉诺塔III

汉诺塔III Problem Description 约19世纪末&#xff0c;在欧州的商店中出售一种智力玩具&#xff0c;在一块铜板上有三根杆&#xff0c;最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上&#xff0c;条件是一次只能移动一…

HDU 小兔的棋盘(卡特兰数)

小兔的棋盘 Problem Description 小兔的叔叔从外面旅游回来给她带来了一个礼物&#xff0c;小兔高兴地跑回自己的房间&#xff0c;拆开一看是一个棋盘&#xff0c;小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0&#xff0c;0)走到终点(n,n)的最短路径数是C(2n,n),…

HDU 2068(错排)

RPG的错排 Problem Description 今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜&#xff0c;第一次猜&#xff1a;R是公主&#xff0c;P是草儿&#xff0c;G是月野兔&#xff1b;第…

HDU 2069

hdu 2069 Coin Change&#xff08;完全背包&#xff09; Coin Change Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 16592 Accepted Submission(s): 5656 Problem Description Suppose there are 5 types of coins…

单词数(set,map)

Problem Description lily的好朋友xiaoou333最近很空&#xff0c;他想了一件没有什么意义的事情&#xff0c;就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。 Input 有多组数据&#xff0c;每组一行&#xff0c;每组就是一篇小文章。每篇小文章…

HDU 几何问题

甜甜从小就喜欢画图画&#xff0c;最近他买了一支智能画笔&#xff0c;由于刚刚接触&#xff0c;所以甜甜只会用它来画直线&#xff0c;于是他就在平面直角坐标系中画出如下的图形&#xff1a; 甜甜的好朋友蜜蜜发现上面的图还是有点规则的&#xff0c;于是他问甜甜&#xff1a…

HDU 汉诺塔IV(递推)

Description 还记得汉诺塔III吗&#xff1f;他的规则是这样的&#xff1a;不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)&#xff0c;也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢&#xff1f;&#xff08;…

二、矩阵分解、正则化

有如下R(5,4)的打分矩阵&#xff1a;&#xff08;“-”表示用户没有打分&#xff09; 其中打分矩阵R(n,m)是n行和m列&#xff0c;n表示user个数&#xff0c;m行表示item个数 那么&#xff0c;如何根据目前的矩阵R&#xff08;5,4&#xff09;如何对未打分的商品进行评分的预测&…