当前位置:首页 > 题解目录 > 正文内容

【题解】区间和

亿万年的星光5年前 (2021-05-01)题解目录22660

1.区间和(sum.cpp)

【描述】

输入一个整数Q,进行Q次询问,每次给定两个整数lr每一次输出lr中所有平方数的和 % 1000000007

【输入】

第一行是一个整数Q

后面的Q行每行有2个数字lr

【输出】

Q行,每行一个整数。

【样例输入输出】

light.in

light.out

2

2   10

3   100

13

384

 

【数据范围】

40%的数据:Q<=1000,l<=r<=1000

80%的数据:Q<=1000,l<=r<=1e6

100%的数据: Q<=1e6,l<=r<=1e6

【题目分析】

  • 用到了一点数论的知识,题目范围比较大的时候考虑使用(a*b)%p =(a%p *b%p)%p

  • “平方数”的意思就是两个一样的数的积。即a*a=b。那么b就是一个平方数


【参考答案1】

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int Q;
    long long int l, r, sum;//输入左边界右边界,防止int 不够
    int ans;
    cin>>Q;
    for(int i=0; i<Q; i++)
    {
        cin>>l>>r;//平方数所在范围
        sum = 0;//每次都得初始化
        long long  temp;
        for (int i = l; i <= r; i++)//判断平方数
        {
   temp = sqrt(i);
   if (temp * temp == i)
    sum += temp * temp;
        }
        ans = sum%1000000007;
        cout<<ans<<endl;


    }
    return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

标签: 模拟数论
分享给朋友:

相关文章

【题解】括号匹配问题

【题目描述】在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括...

【题解】老王赛马

【题目描述】赛马是一古老的游戏,早在公元前四世纪的中国,处在诸侯割据的状态,历史上称为“战国时期”。在魏国作官的孙膑,因为受到同僚庞涓的迫害,被齐国使臣救出后,到达齐国国都。 赛马是当时最受...

求Π的值

【题目描述】根据公式:arctanx(x)=x−x^3/3+x^5/5−x^7/7+…和π=6arctanx(1/√3).定义函数arctanx(x),求当最后一项小于10^(−6)时π的值。【输入描...

【题解】公交乘车

【题解】公交乘车

【题目描述】A城市有一条非常特别的街道,该街道在每个公里的节点上都有一个公交车站,乘客可以在任意的公交站点上车,在任意的公交站点下车。乘客根据每次乘坐公交的公里数进行付费,比如,下表就是乘客乘坐不同的...

【题解】后缀表达式的值

【题解】后缀表达式的值

【题目描述】从键盘读入一个后缀表达式(字符串),只含有0-9组成的运算数及加(+)、减(—)、乘(*)、除(/)四种运算符。每个运算数之间用一个空格隔开,不需要判断给你的表达式是否合法。以@作为结束标...

八皇后问题

八皇后问题

【题目描述】八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行...