快速幂——while理解&&[P1965] 转圈游戏

快速幂——while理解

\[a^k
\]

把k转成2进制

\[k=2^n*p[n]+2^(n-1)*p[n-1]+...+2^1*p[1]+2^0*p[0]
\]

\[a^k=a^(2^n*p[n]+2^(n-1)*p[n-1]+...+2^1*p[1]+2^0+p[0])
\]

\[a^k=a^(2^0*p[0])*a^(2^1*p[1])*a^(2^2*p[2])*...*a^（2^n*p[n]）
\]

\[a^k=a^2^0^p[0]*a^2^1^p[1]*a^2^2^p[2]*...*a^2^n^p[n]
\]

p[0...n]不是一就是零

一开始a=a,若p[0]=1,ans就乘a

接着循环，a=a^{2,若p[1]=1，ans就乘a}2

以此类推

直到第n项

	int a;

	int ans = 1;

	while(k)

	{

		if(k % 2 == 1)	ans *=a;

		k /= 2;

		a *= a;

	}

转圈游戏

裸快速幂

#include <cmath>

#include <cstdio>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

int a, n, m, x, k;

long long mi;

int QR()

{

	char c;

	int sign = 1;

	c = getchar();

	while (c < '0' ||c > '9'){

		if(c == '-')

			sign = -1;

		c = getchar();

	}

	int res = 0;

	while(c <= '9' &&c >= '0'){

		res *= 10;

		res += c - '0';

		c = getchar();

	}

	res *= sign;

	return res;

}

int main()

{

	n=QR();

	m=QR();

	k=QR();

	x=QR();

	a = 10;

	mi = 1;

	while(k)

	{

		if(k % 2 == 1)	mi *=a;

		k /= 2;

		a *= a;

		a %= n;

		mi %= n; //必须随时取模，不然超ll

	}

	mi *= m;

	mi += x;

	mi %= n;

	printf("%lld",mi);

	return 0;

}

巴特西

快速幂——while理解&&[P1965] 转圈游戏

快速幂——while理解

转圈游戏

最新文章

热门文章