文档章节

Codevs 取余运算

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 568
阅读 0
收藏 0

点击就送屠龙宝刀
题目描述 Description
输入b,p,k的值,编程计算bp mod k的值。其中的b,p,k*k为长整型数(2^31范围内)。

输入描述 Input Description
b p k

输出描述 Output Description
输出b^p mod k=?

=左右没有空格

样例输入 Sample Input
2 10 9

样例输出 Sample Output
2^10 mod 9=7

只能说codevs数据好水。。快速幂都能过。。首先我们来讨论正解。
已知b^p mod k =b mod k ^ pmod k 但是这样还是存在炸long long 的情况。然后我们继续优化。因为有a*b mod c = (a mod c)*(b mod c) 所以我们可以把b^p拆成p个b相乘。然后你发现因为k*k在int内可以过了。。
那我们再来扩展这道题。如果k*k超过了long long 该怎么办呢?(其实是有例题的但是我懒得找了。。。) 我们可以用二进制的思想,把p拆成2^ai+2^bi+2^ci……+2^0.因为mod操作满足(a+b)mod c =(a mod c +b mod c) mod c 那么我们就可以得到答案了。(什么?输入的是高精?敲个高精加高精模高精乘不就完了??)

废话不说了贴这道题代码。。(傻逼快速幂的题目。。难度钻石)

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int maxn=(int)1e5+10,MOD=99999997;

int n;
int p[maxn];
long long  c[maxn];

int fuckdc(int i)
{
     return i&(-i);
}

long long  sum(int wtf)
{
    long long dc=0;
    while(wtf>0) dc+=c[wtf],wtf-=fuckdc(wtf);
    return dc;
}

long long  add(int i,int x)
{
    while(i<=n) c[i]+=x,i+=fuckdc(i);
}
struct Node{
    int num,id;
    int dc(int a,int b){ num=a,id=b;}
}dc[maxn],wtf[maxn],fuck_[maxn];

bool operator <(Node a,Node b)
{
    return a.num^b.num?a.num>b.num:a.id>b.id;
}

int main()
{
    int i,x;
    long long  ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&x),dc[i].dc(x,i);
    for(int i=1;i<=n;i++) scanf("%d",&x),wtf[i].dc(x,i);
    sort(dc+1,dc+n+1);
    sort(wtf+1,wtf+n+1);
    for(int i=1;i<=n;i++) fuck_[dc[i].id].dc(n-i+1,dc[i].id),p[n-i+1]=wtf[i].id;
    for(int i=1;i<=n;i++) dc[i].dc(p[fuck_[i].num],i);
    sort(dc+1,dc+n+1);
    for(int i=1;i<=n;i++) ans+=sum(dc[i].id),ans%=MOD,add(dc[i].id,1);
    printf("%lld",ans);
    return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/49274899

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
汇编总结:无符号除法,有符号除法,取余,无符号乘法,有符号乘法指令

本文分为3个模块。 示例---该指令的示例 解释---为指令不好理解的地方 练习---为了更熟悉该指令 1.1 有符号除法指令及取余example: 在c语言里要完成 8 / 2的汇编指令如下: 在c语言里要完成 ...

guonaihong
2015/10/07
1K
0
python学习之数字

coerce() 内建函数来帮助你实现这种转换 *位运算符(只适用于整数) 位运算符 功能 ~num 单目运算,对数的每一位取反。结果为 num1 << num2 Num1 左移 num2 位 num1 >> num2 Num1 右移 num2...

happyliferao
2015/10/12
20
0
算法学习之路|逆元取模(一)

好了,今天轻松一点。逆元取模,一个小概念,在做ACM一些题目的时候必须要用到。终于下决心好好看一看了 ! 学习过程中遇到了模幂运算,即先进行幂运算,再进行模运算。转载自百度百科 概念:...

kissjz
2018/02/10
0
0
小蚂蚁学习C语言(6)——C语言运算符

运算符 算数运算符 + - / %(取余数) 关系运算符 > < >= <= != == 逻辑运算符 !(非) && (与) || (或) !真 就是假 !假 就是真 真&&真 真 真&&假 假 假&&假 假 真||假 真 假||真 真 真...

嗜学如命的小蚂蚁
2015/12/02
86
0
随机0-35六次和随机0-2176782335(36的六次方)重复率相差很大的问题

昨天有一个需求 生成六位数字字母组成的激活码 重复率越小越好 ---------------------------------以上是背景 简单 不要求长度可以使用uuid或md5值 要求六位 就随机吧 有两种方案 1 随机0-3...

强船生
2015/08/04
350
10

没有更多内容

加载失败,请刷新页面

加载更多

调用约定

对于常见的指令集,在指令层面没有所谓的“函数”概念,只有“子程序”概念。子程序是存储在“主程序”之外的一段指令。子程序通过call指令调用,通过ret指令返回。子程序可以使用内存、堆栈...

tommwq
43分钟前
3
0
设计类题目

1. 订单 和 退货单之间有什么关系? 答:退货单是 用 用户提交退货 和 订单生成的 或者 订单和退货单都是一张单子,用一个状态标识 2. 在这种由源头单生成的流程中,第二张单子是怎样生成的?...

杨凯123
58分钟前
5
0
读写锁分离

java.util.concurrent.locks包定义了两个锁类, 我们已经讨论的ReentrantLock类和 ReentrantReadWriteLock 类。 如果很多线程从一个数据结构读取数据而很少线程修改其中数 据的话, 后者是十...

ytuan996
今天
6
0
金钱焦虑症测试 -- 人人都有吧?

你经常觉得钱不够花,被金钱困扰着吗?试试这个焦虑量表测试,测试一下你的金钱焦虑指数吧。请选择选一个最适合自己态度的答案。买买买的欲望高吗?又是一个节日,有打折活动;又被种草一个化...

蛤蟆丸子
今天
4
0
JAVA-LOCK之底层实现原理(源码分析)

首先和Synchronized(可以参考) 的不同之处,Lock完全用Java写成,在java这个层面是无关JVM实现的。其实现都依赖java.util.concurrent.AbstractQueuedSynchronizer类,简称AQS。 简单说来,...

小海bug
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部