qscoj 128 喵哈哈村的魔法源泉(2)(模仿快速幂,好题)

喵哈哈村的魔法源泉(2)

发布时间: 2017年5月9日 20:59   最后更新: 2017年5月9日 21:00   时间限制: 1000ms   内存限制: 128M

描述

喵哈哈村有一个魔法源泉,里面有无穷无尽的力量。

但是前提是你能答出这样一个问题:

给你a,b,p,让你输出a*b%p的值。

输入

本题包含若干组测试数据。 第一行三个整数a,b,p。 满足:0<=a,b,p<=1e18

输出

输出答案

样例输入1 复制

10 1 7

样例输出1

3
题目链接:http://qscoj.cn/problem/128/
题解:卿学姐说首先快速幂是来处理次方的问题,那么我们模仿快速幂,写一个快速加即可,这样我们每次乘以2,就不会爆longlong了
这里要注意,没加while会WA,这里卡就卡这个!
下面给出AC代码:
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll a,b,p;
 5 ll gcd(ll a,ll b)//模仿快速幂解法
 6 {
 7     if(b==0)
 8         return 0;
 9     ll res=gcd(a,b/2);
10     res=(res+res)%p;
11     if(b&1)
12         return (res+a)%p;
13     else
14         return res;
15 }
16 int main()
17 {
18     while(scanf("%lld%lld%lld",&a,&b,&p)!=EOF)
19     {
20        cout<<gcd(a,b)<<endl;
21     }
22     return 0;
23 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

Android动态加载入坑指南

曾几何时,国内各大公司掀起了一股研究Android动态加载的技术,两年多过去了,动态加载技术俨然成了Android开发中必须掌握的技术。那么动态加载技术是什么呢...

25810
来自专栏我是业余自学C/C++的

redis_3.0.7_sds.c_sdsull2str()

1604
来自专栏一个会写诗的程序员的博客

SpringBoot AOP 记录日志实例

面向切面编程(AOP是Aspect Oriented Program的首字母缩写) ,我们知道,面向对象的特点是继承、多态和封装。而封装就要求将功能分散到不同的...

5851
来自专栏青玉伏案

关于Simple_html_dom的小应用

  今天一同学给我推荐了本书,说是刚出不久,内容还不错,是心灵鸡汤类的书,于是按捺不住就像在网上下一本,可是木有资源肿么办。只有在线看的,作为一个准码农,所以甭...

2177
来自专栏JAVA后端开发

flowable实现多实例节点的自由跳转

最近弃用activiti,改用flowable,发现在实现多节点实例自由跳转时,有很大区别。 自由跳转整理如下:

5482
来自专栏有趣的django

PYTHON面试

大部分的面试问题,有最近要找事的老铁吗?  python语法以及其他基础部分 可变与不可变类型;  浅拷贝与深拷贝的实现方式、区别;deepcopy如果你来...

6237
来自专栏安恒网络空间安全讲武堂

Writeup丨国赛线上初赛解题最后一波~

1594
来自专栏高性能服务器开发

服务器开发通信协议设计介绍

由于我们的即时通讯软件的用户存在用户状态问题,即用户登录成功以后可以在他的好友列表中看到哪些好友在线,所以客户端和服务器需要保持长连接状态。另外即时通讯软件一般...

1782
来自专栏Android知识点总结

1--安卓网络编程之获取IP地址

2612
来自专栏程序员阿凯

JDK10 揭秘

1485

扫码关注云+社区