连续取模
2018-06-17 23:22:41来源:未知 阅读 ()
problem E . Mod
Kim刚刚学会C语言中的取模运算(mod)。他想要研究一下一个数字A模上一系列数后的结果是多少。帮他写个程序验证一下。
Input
第一行一个整数T代表数据组数。
接下来T组数据,第一行一个整数n,接下来n个数字ai
接下来一行一个整数m,接下来m个数字bi
Output
对于每个bi,输出bi%a1%a2%...%an
Sample
Input |
Output |
1 4 10 9 5 7 5 14 8 27 11 25 |
4 3 2 1 0 |
Hint
在C语言中,A mod B 是 a%b
样例解释:
14%10%9%5%7=4
8%10%9%5%7=3
...
数据范围:
1<=n<=100000
1<=m<=100000
1<=ai<=1000000000
0<=bi<=1000000000
思路:当x连续对一个数列An取模时,结果等于对首项起的递减数列Bn取模。因为如果对一个小数取模后再对一个大数取模,那么第二次的操作后结果并没有变化。
之后,用二分找到与x最接近且小于等于的Bn项,用x模上它,重复这个过程。
#include "cstdio" #include "algorithm" #include "cstring" int s[100000],d[100000]; int b[100000]; int main() { int t,n,m; scanf("%d",&t); while (t--){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&s[i]); } scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%d",&d[i]); } } b[0]=s[0]; int k=0; for(int i=1;i<n;i++){ if(b[k]>s[i]){ b[++k]=s[i]; } } for(int i=0;i<m;i++){ int l=0,x=d[i]; while (l!=k){ int r=k; while (r>l){ int mid=(l+r)/2; if(x<b[mid]){ l=mid+1; } else{r=mid;} } x%=b[l]; } printf("%d\n",x); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- DSA_04:链表 2020-03-28
- 标准输入重定向到文件后,如何连续读入,如何判断标准输入流 2020-03-20
- 哈尔滨网络热身赛 2019-11-25
- 两个数的差 2019-10-16
- C++负数类型转换,-1对256取模 2019-09-23
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash