洛谷U32670 小凯的数字(比赛)
题目网址
https://www.luogu.org/problemnew/show/U32670
题目背景
NOIP2018 原创模拟题T1
NOIP DAY1 T1 or DAY 2 T1 难度
是否发现与NOIP2017 DAY1 T1 有异曲同工之妙
题目描述
小凯有一天突发奇想,写下了一串数字:l(l+1)(l+2)...(r-1)rl(l+1)(l+2)...(r−1)r
例如:l=2,r=5时,数字为:23452345
l=8,r=12时数字为:8910111289101112
小凯很喜欢数字9,所以他想问你他写下的数字除以9的余数是多少
例如:l=2,r=5时,2345 mod 9 = 5
输入输出格式
输入格式:
第一行为数字Q,表示小凯有Q个问题
第2-Q+1行,每行两个数字 l,r 表示数字范围
输出格式:
对于每行的问题输出一行,一个数字,表示小凯问题的回答
输入输出样例
2
2 5
8 12
5
5
3
1 999
123 456
13579 24680
0
6
0
说明
样例1解释:2345 mod 9 = 5 89101112 mod 9 = 5
30% 数据满足:Q<=10;l,r<=100
50% 数据满足:Q<=100;l,r<=10000
70% 数据满足:Q<=1000;l,r<=10^6
100%数据满足:Q<=10000;l,0<r<=10^12且 l<=r
题解
根据本题的数据范围,不难发现一定是一道数论题。这一题的难度和NOIP提高组day1的第一题水平差不多,所以应该不是很难;
解决本题,首先要知道:
定理1、能被9整除的数各位数字之和能被9整除;
定理2、如果有9*n(n为自然数)个连续的数字(如题意,比如123456789),那么该数一定能被9整除
第一点很好理解,其实第二点也同样如此,根据高斯求和公式,(首项+末项)*项数/2,
有计算经验的同学一定知道,(首项+末项)和项数中一定有一个是2的倍数,所以不存在带余除法,
那么因为项数是9的倍数,所以上述公式(首项+末项)*项数/2,一定是9的倍数,所以定理2成立。
那么,根据这两个定理,本题代码就很好写了。
再整理一遍思路:
1.读入问题数量Q,循环Q次,每次读入l和r;
2.计算出数字个数(即r-l+1的值),并对9取余,即定义一个变量cnt=(r-l+1)%9;
3.从r开始,往前依次枚举cnt次(因为cnt对9取过模,所以最多循环9次)
将枚举出的数字对9取余,加入sum中;
4.输出sum对9取余即可
5.本题还有一个细节:要用long long
代码
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long using namespace std; int Q;
ll l,r; void work()
{
scanf ("%d",&Q);
while (Q--)
{
scanf ("%lld%lld",&l,&r);
ll cnt=(r-l+)%;
ll sum=;
for (ll i=,k=r;i<=cnt;i++,k--)
sum+=k%;
printf ("%lld\n",sum%);
}
return;
} int main()
{
work();
return ;
}
出处:https://www.cnblogs.com/yujustin/
最新文章
- 大三那年在某宝8块钱买的.NET视频决定了我的职业生涯
- networkcomms 相关文章(转载)
- MVCC PostgreSQL实现事务和多版本并发控制的精华
- ruby formatting time
- svn的merge使用例子
- ggplot2 theme相关设置—线条设置
- Javascript数组与基本函数
- 区间DP的四边形不等式优化
- Socket编程实践(11) --epoll原理与封装
- utl_file包的使用
- 【原创】大数据基础之Spark(2)Spark on Yarn:container memory allocation容器内存分配
- Linux内核原理与分析-第一周作业
- [LeetCode] Chalkboard XOR Game 黑板亦或游戏
- [android] listview入门
- .Net外包篇:我是如何看待外包的
- mybatis cloud not autowired
- D. Too Easy Problems
- 浮动IP(FLOAT IP)
- 【转载】C#之玩转反射
- String 简介
热门文章
- RedHat 6.4源码方式安装mysql5.5
- LAB2 软件测试 Selenium上机实验 2017
- NO.009-2018.02.14《临江仙&#183;送钱穆父》宋代:苏轼
- Jerry的WebClient UI 42篇原创文章合集
- HDU 4117 GRE Words
- LA 4043 最优匹配
- luogu P4168 [Violet]蒲公英
- POJ 1190 生日蛋糕 【DFS + 极限剪枝】
- 推荐一个zookeeper信息查看工具
- 浅谈二分查找 JavaScript