shuoj-1942: yaoge and xyiyy's interesting game-数学-快速幂

2023-12-22 17:32

本文主要是介绍shuoj-1942: yaoge and xyiyy's interesting game-数学-快速幂,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

xyiyy和yaoge正在做一个游戏。现在yaoge面临这游戏中关键的一步,如果不能算出这个结果,那么他将要付出一块鸡排的代价。

现在yaoge有两个数A和B,yaoge对这两个数进行k次操作,每次操作定义如下:

若A≤B,则B = B - A,A = A + A

若A>B,则A = A - B,B = B + B

现要求求出k次操作之后较小的那个数的值

Input

多组数据,每组数据有一行

每行有三个整数A,B,k,用空格隔开。

1≤A≤10^9,1≤B≤10^9,1≤k≤2*10^9

Output

对于每组数据,输出k次操作后较小的数的值并换行

Sample Input

2 6 1
5 5 3

Sample Output

4

0

Source

xyiyy

解题思路::这道题主要看思路,没有思路想几个小时都弄不下来,有了思路就很快。由题知 (A + B)的值是不会改变的,设c = (A + B )避免在A,B变化的过程中改变(A + B )

若A≤B,则B = B - A,A = A + A;所以B = ( B - A + A + B )mod( c ) = ( B + B )mod(c ),A = ( A + A )mod( c )

 若A>B,则A = A - B,B = B + B;所以 A = ( A - B + A + B )mod(c ) = ( A + A )mod( c ),B = ( B + B )mod( c ) 

所以A = ( A + A )mod( c ),B = ( B + B )mod( c )

当第k次操作的时候A = A * 2 ^ K mod (c ) , B = B * 2 ^ K mod ( c)(写成B= c - A也可) ;然后比较大小,输出小值问题搞定。

#include <iostream>
#include <sstream>
#include <ios>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cctype>
using namespace std;
#define XINF INT_MAX
#define INF 0x3FFFFFFF
#define MP(X,Y) make_pair(X,Y)
#define PB(X) push_back(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define REP2(X,L,R) for(int X=L;X<=R;X++)
#define DEP(X,R,L) for(int X=R;X>=L;X--)
#define CLR(A,X) memset(A,X,sizeof(A))
#define IT iterator
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<int> VI;
//const int MAXN = 10010;
//#define INF 0x3FFFFFFF
const ll MOD = 1000000007;
//b = (b-a)%(b+a) = (b-a+a+b)%(b+a) = (b+b)%(a+b);a = a+a = (a+a)%(a+b)//执行一次
//b = b*2^k%(a+b);a = a*2^k%(a+b)//执行k次
ll a,b;
int k;
//快速幂规则::a*13 = a * a^4 *a^8 ;13 = 1101(2) = 1(2) + 100(2) +1000(2) = 1 + 4 + 8
ll fast_mod(ll n,ll m,ll c){ //求快速幂ll ret=1; while(m){ if(m&1)ret = ret*n%c; n=n*n%c;//这里保证m的移位和n的幂数对等,右移x位就为n的2^x次幂 m>>=1; } return ret; 
} 
int main(){while(cin>>a>>b>>k){ll c = a+b;//避免在a,b值改变过程中(a+b)的值改变b = b*fast_mod(2,k,c)%(c);a = a*fast_mod(2,k,c)%(c);	cout<<((a>b)?b:a)<<endl;}return 0;
}


 

 

这篇关于shuoj-1942: yaoge and xyiyy's interesting game-数学-快速幂的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/524832

相关文章

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

v0.dev快速开发

探索v0.dev:次世代开发者之利器 今之技艺日新月异,开发者之工具亦随之进步不辍。v0.dev者,新兴之开发者利器也,迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势,助汝速速上手,提升开发之效率。 何谓v0.dev? v0.dev者,现代化之开发者工具也,旨在简化并加速软件开发之过程。其集多种功能于一体,助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

fzu 2275 Game KMP

Problem 2275 Game Time Limit: 1000 mSec    Memory Limit : 262144 KB  Problem Description Alice and Bob is playing a game. Each of them has a number. Alice’s number is A, and Bob’s number i

利用Django框架快速构建Web应用:从零到上线

随着互联网的发展,Web应用的需求日益增长,而Django作为一个高级的Python Web框架,以其强大的功能和灵活的架构,成为了众多开发者的选择。本文将指导你如何从零开始使用Django框架构建一个简单的Web应用,并将其部署到线上,让世界看到你的作品。 Django简介 Django是由Adrian Holovaty和Simon Willison于2005年开发的一个开源框架,旨在简