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

【题解】区间和

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

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


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

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

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

相关文章

【题解】黑色联通块

【题解】黑色联通块

【题目描述】输入一个n×n的黑白图像(1表示黑色,0表示白色),任务是统计其中黑色连通块的个数。如果两个黑格子有公共边或者公共顶点,就说它们属于同一个联通块。如下图所示的图形有3个联通块。【输入描述】...

【题解】AC

4.AC(ac.cpp) 【问题描述】 小明获得了一行字符串,他想知道在不改变字符顺序的情况下,从前到后最多能组合出多少个ac? (a和c的位置可以不连续)比如:字符串为addca...

【题解】河中跳房子

【题目描述】每年奶牛们都要举办各种特殊版本的跳房子比赛,包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行,在起点和离起点L远 (1 ≤ L≤ 1,000,000,000...

【题解】最大配对

题目描述      给出2个序列A={a[1],a[2],…,a[n]},B={b[1],b[2],…,b[n]},从A、B中各选出n个元素进行一一配对(可以不按照原来在...

【题解】大数取模

【题目描述】求m%n。【输入描述】两个数,m和n。【输出描述】m模n的值。【样例输入】3【样例输出】2【数据范围】对于30%的数据, 1<m<10^18对于70%的数据, m>10^...

【题解】进制转换(2019青岛市程序设计竞赛)

【问题描述】输入十进制正整数n和k,输出n的k进制数。我们熟悉的十进制所需的10个基数(基本的数字符号)是0,1,2,3,4,5,6,7,8,9。当10<k<=16时,k进制的k个基数从小...