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

【题解】区间和

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

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;
}


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

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

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

相关文章

字符串移位包含问题

【题目描述】对于一个字符串来说,定义一次循环移位操作为:将字符串的第一个字符移动到末尾形成新的字符串。给定两个字符串 s_1s1 和 s_2s2,要求判定其中一个字符串是...

【题解】网线主管

【题目描述】仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成,他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起,即将它们全部连到一个单一的中心服务器。为...

【算法】滑动窗口2—窗口大小可变

【算法】滑动窗口2—窗口大小可变

对于滑动窗口第二类:窗口大小可变类型 图解如下,类似双指针算法。【解题思想】1、字符串 S 中使用双指针的左右指针技巧,初始化 left = right = 0,把索引的...

【题解】剔除相关数

【题目描述】一个数与另一个数如果含有相同数字和个数的字符,则称两数相关。现有一堆乱七八糟的整数,里面可能充满了彼此相关的数,请你用一下手段,自动地将其剔除。【输入描述】每组数据前有一个N(<10...

【题解】单词排序

【题目描述】输入一行单词序列,相邻单词之间由一个或者多个空格间隔,请按照字典序输出这些单词,要求重复的单词只输出一次。(区分大小写)【输入描述】一行单词序列,最少一个单词,最多100个单词,每个单词长...

【题解】金银岛

题目描述某天KID利用飞行器飞到了一个金银岛上,上面有许多珍贵的金属,KID虽然更喜欢各种宝石的艺术品,可是也不拒绝这样珍贵的金属。但是他只带着一个口袋,口袋至多只能装重量为w的物品。岛上金属有s个种...