【大数取模】HDOJ-1134、CODEUP-1086

时间:2022-09-20 18:44:56

1086: 大数取模

 

题目描述

现给你两个正整数A和B,请你计算A mod B。
为了使问题简单,保证B小于100000。

输入

输入包含多组测试数据。每行输入包含两个正整数A和B。A的长度不超过1000,并且0<B<100000。

输出

对于每一个测试样例,输出A mod B。

样例输入

2 3
12 7
152455856554521 3250

样例输出

2
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++ 的大数类,大数模板
    C++ 大数模板 链接:http://www.cnblogs.com/zhengbin/p/4368182.html

    代码:

 #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的更多相关文章

  1. hdu2302&lpar;枚举,大数取模&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2303 题意:给出两个数k, l(4<= k <= 1e100, 2<=l<=1 ...

  2. &lpar;POJ2635&rpar;The Embarrassed Cryptographer&lpar;大数取模&rpar;

    The Embarrassed Cryptographer Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 13041 Accep ...

  3. HDU4704Sum 费马小定理&plus;大数取模

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4704 题目大意: 看似复杂,其实就是求整数n的划分数,4=1+1+2和4=1+2+1是不同的.因而可 ...

  4. HDU--1212大数取模

    大数取模问题.题目传送门:HDU1212 #include <iostream> using namespace std; char a[1010]; int main() { int b ...

  5. ACM-ICPC 2018 焦作赛区网络预赛G Give Candies(隔板定理 &plus; 小费马定理 &plus; 大数取模,组合数求和)题解

    题意:给你n个东西,叫你把n分成任意段,这样的分法有几种(例如3:1 1 1,1 2,2 1,3 :所以3共有4种),n最多有1e5位,答案取模p = 1e9+7 思路:就是往n个东西中间插任意个板子 ...

  6. HPU 1471:又是斐波那契数列??(大数取模)

    1471: 又是斐波那契数列?? 时间限制: 1 Sec 内存限制: 128 MB 提交: 278 解决: 27 统计 题目描述 大家都知道斐波那契数列吧?斐波那契数列的定义是这样的: f0 = 0; ...

  7. 题解报告:hdu 1212 Big Number(大数取模&plus;同余定理)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1212 Problem Description As we know, Big Number is al ...

  8. HDU-2303 The Embarrassed Cryptographer 高精度算法(大数取模)

    题目链接:https://cn.vjudge.net/problem/HDU-2303 题意 给一个大数K,和一个整数L,其中K是两个素数的乘积 问K的是否存在小于L的素数因子 思路 枚举素数,大数取 ...

  9. HDU-1226-超级密码-队列&plus;广搜&plus;大数取模

    Ignatius花了一个星期的时间终于找到了传说中的宝藏,宝藏被放在一个房间里,房间的门用密码锁起来了,在门旁边的墙上有一些关于密码的提示信息: 密码是一个C进制的数,并且只能由给定的M个数字构成,同 ...

随机推荐

  1. 深入浅出UML类图(一)

    在UML 2.0的13种图形中,类图是使用频率最高的UML图之一.Martin Fowler在其著作<UML Distilled: A Brief Guide to the Standard O ...

  2. 大数据之sqoop

    一.安装: 1 解压然后把mysql的驱动放在$SQOOP_HOME/lib 目录中2. conf/sqoop-en.sh export HADOOP_COMMON_HOME=/home/hadoop ...

  3. Ajax案例:三级联动查询员工的信息&lpar;三张表进行内连接&rpar;

    需求分析: 通过数据库连接池,可以查询到数据库中员工的各种信息,通过点击下拉框的方式实现三级联动,即:没有点击city下拉框,后面两个下拉框中没有值,这样,点击city下拉框,department下拉 ...

  4. Java开发工具IntelliJ IDEA单元测试和代码覆盖率图解

    原文 http://www.cnblogs.com/xiongmaopanda/p/3314660.html Java开发工具IntelliJ IDEA使用教程:单元测试和代码覆盖率 本文将展示如何使 ...

  5. hdu1536Nim

    sg函数打表的基础应用,第一道ac的sg函数打表题纪念下,直接上代码: hdu1536题目连接 #include<iostream> #include<cstdio> #inc ...

  6. Android切换前后置摄像头并录制视频

    项目需要对微信的视频模块也看了一下,在此就对这块进行了一个开发.首先给出效果图 首先给出java代码 /** * RecordActivity.java * 版权所有(C) 2013 * 创建:cui ...

  7. mac pfctl &sol; centos iptables 使用

    mac使用pfctl 为了测试zk client的重连功能,需要模拟zk client与zk server网络连接出现问题的情况,经过查询资料发现可以使用防火墙阻止zk server启动端口上的流量实 ...

  8. 如何实现Activiti的分支条件的自定义配置&lpar;转&rpar;

    如何实现Activiti的分支条件的自定义配置 博客分类: Activiti Java SaaS   一.Activiti的流程分支条件的局限 Activiti的流程分支条件目前是采用脚本判断方式,并 ...

  9. pip常用记录

    同电脑多版本python python2 -m pip install 包名(python2指向2.7的python.exe) 指定版本 pip install 包名==版本号 指定源 pip ins ...

  10. SPOJ GSS

    GSS1 题目大意:给出一个数列,多次询问区间最长连续子段和 题解:线段树维护区间最长连续子段和gss,区间从最左元素开始的最长连续子段和lgss 区间以最右元素为结尾的最长连续子段和rgss以及区间 ...