1086: 大数取模
题目描述
为了使问题简单,保证B小于100000。
输入
输出
样例输入
12 7
152455856554521 3250
样例输出
5
1521
【概念】
(a+b)%n =(a%n+b%n)%n
(a-b)%n = (a%n-b%n)%n
实话说刚开始我没看懂。
代码:
int mod(char str[],int num)
{
int number[MAXN],i,d = ;
int len = strlen(str);
//将字符串数组转化为数字数组
for(i = ;i < len;i++)
number[i]=str[i]-'';
int remainder=;
for(i = ;i < len;i++)
{
remainder=(remainder * + number[i]) % num;
}
return remainder;
}
举个例子:
123 % 4 = 3
-1- (0 * 10 + 1) % 4 = 1; -2- (1 * 10 + 2) % 4 = 0;
-3- (0 * 10 + 3) % 4 = 3; -4- 得到最终结果3
也就是模拟了除法竖式的过程
【练习题】
- 题目链接:http://arena.acmclub.com/problem.php?id=1086
代码:
#include<cstdio>
#include<cstring>
const int MAXN = ;
int mod(char str[],int num)
{
int number[MAXN],i,d = ;
int len = strlen(str);
//将字符串数组转化为数字数组
for(i = ;i < len;i++)
number[i]=str[i]-'';
int remainder=;
for(i = ;i < len;i++)
{
remainder=(remainder * + number[i]) % num;
}
return remainder;
}
int main(){
char A[MAXN];
int B;
//'~'取反符号,当输入值不符合要求时停止
//while(~scanf("%s %d",A,&B)){ //判断有无结尾符结束
//while(scanf("%s %d",A,&B) != EOF){ //如果两个参数均被读入则返回参数个数
while(scanf("%s %d",A,&B) == ){
printf("%d\n",mod(A,B));
}
return ;
}
- 下面这种方法是运用到了C++ 的大数类,大数模板
代码:
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = ;
const int DLEN = ;
char str[];
int modd;
class BigNum{
private:
int a[];
int len;
public:
BigNum(){len = ;memset(a,,sizeof(a));}
BigNum(const char*);
int operator %(const int &)const;
};
BigNum::BigNum(const char*s) //将一个字符串类型的变量转化为大数
{
int t,k,index,l,i;
memset(a,,sizeof(a));
l=strlen(s);
len=l/DLEN;
if(l%DLEN)
len++;
index=;
for(i=l-;i>=;i-=DLEN)
{
t=;
k=i-DLEN+;
if(k<)
k=;
for(int j=k;j<=i;j++)
t=t*+s[j]-'';
a[index++]=t;
}
}
int BigNum::operator %(const int & b) const{ //大数对一个int类型的变量进行取模运算
int i,d=;
for (i = len-; i>=; i--)
{
d = ((d * (MAXN+))% b + a[i])% b;
}
return d;
}
int main(){
while(~scanf("%s %d",str,&modd)){
BigNum big(str);
cout << big % modd << endl;
}
return ;
}
【大数取模】HDOJ-1134、CODEUP-1086的更多相关文章
-
hdu2302(枚举,大数取模)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2303 题意:给出两个数k, l(4<= k <= 1e100, 2<=l<=1 ...
-
(POJ2635)The Embarrassed Cryptographer(大数取模)
The Embarrassed Cryptographer Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 13041 Accep ...
-
HDU4704Sum 费马小定理+大数取模
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4704 题目大意: 看似复杂,其实就是求整数n的划分数,4=1+1+2和4=1+2+1是不同的.因而可 ...
-
HDU--1212大数取模
大数取模问题.题目传送门:HDU1212 #include <iostream> using namespace std; char a[1010]; int main() { int b ...
-
ACM-ICPC 2018 焦作赛区网络预赛G Give Candies(隔板定理 + 小费马定理 + 大数取模,组合数求和)题解
题意:给你n个东西,叫你把n分成任意段,这样的分法有几种(例如3:1 1 1,1 2,2 1,3 :所以3共有4种),n最多有1e5位,答案取模p = 1e9+7 思路:就是往n个东西中间插任意个板子 ...
-
HPU 1471:又是斐波那契数列??(大数取模)
1471: 又是斐波那契数列?? 时间限制: 1 Sec 内存限制: 128 MB 提交: 278 解决: 27 统计 题目描述 大家都知道斐波那契数列吧?斐波那契数列的定义是这样的: f0 = 0; ...
-
题解报告:hdu 1212 Big Number(大数取模+同余定理)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1212 Problem Description As we know, Big Number is al ...
-
HDU-2303 The Embarrassed Cryptographer 高精度算法(大数取模)
题目链接:https://cn.vjudge.net/problem/HDU-2303 题意 给一个大数K,和一个整数L,其中K是两个素数的乘积 问K的是否存在小于L的素数因子 思路 枚举素数,大数取 ...
-
HDU-1226-超级密码-队列+广搜+大数取模
Ignatius花了一个星期的时间终于找到了传说中的宝藏,宝藏被放在一个房间里,房间的门用密码锁起来了,在门旁边的墙上有一些关于密码的提示信息: 密码是一个C进制的数,并且只能由给定的M个数字构成,同 ...
随机推荐
-
深入浅出UML类图(一)
在UML 2.0的13种图形中,类图是使用频率最高的UML图之一.Martin Fowler在其著作<UML Distilled: A Brief Guide to the Standard O ...
-
大数据之sqoop
一.安装: 1 解压然后把mysql的驱动放在$SQOOP_HOME/lib 目录中2. conf/sqoop-en.sh export HADOOP_COMMON_HOME=/home/hadoop ...
-
Ajax案例:三级联动查询员工的信息(三张表进行内连接)
需求分析: 通过数据库连接池,可以查询到数据库中员工的各种信息,通过点击下拉框的方式实现三级联动,即:没有点击city下拉框,后面两个下拉框中没有值,这样,点击city下拉框,department下拉 ...
-
Java开发工具IntelliJ IDEA单元测试和代码覆盖率图解
原文 http://www.cnblogs.com/xiongmaopanda/p/3314660.html Java开发工具IntelliJ IDEA使用教程:单元测试和代码覆盖率 本文将展示如何使 ...
-
hdu1536Nim
sg函数打表的基础应用,第一道ac的sg函数打表题纪念下,直接上代码: hdu1536题目连接 #include<iostream> #include<cstdio> #inc ...
-
Android切换前后置摄像头并录制视频
项目需要对微信的视频模块也看了一下,在此就对这块进行了一个开发.首先给出效果图 首先给出java代码 /** * RecordActivity.java * 版权所有(C) 2013 * 创建:cui ...
-
mac pfctl / centos iptables 使用
mac使用pfctl 为了测试zk client的重连功能,需要模拟zk client与zk server网络连接出现问题的情况,经过查询资料发现可以使用防火墙阻止zk server启动端口上的流量实 ...
-
如何实现Activiti的分支条件的自定义配置(转)
如何实现Activiti的分支条件的自定义配置 博客分类: Activiti Java SaaS 一.Activiti的流程分支条件的局限 Activiti的流程分支条件目前是采用脚本判断方式,并 ...
-
pip常用记录
同电脑多版本python python2 -m pip install 包名(python2指向2.7的python.exe) 指定版本 pip install 包名==版本号 指定源 pip ins ...
-
SPOJ GSS
GSS1 题目大意:给出一个数列,多次询问区间最长连续子段和 题解:线段树维护区间最长连续子段和gss,区间从最左元素开始的最长连续子段和lgss 区间以最右元素为结尾的最长连续子段和rgss以及区间 ...