余爆long long?クイックプラスしてみましょう!【高速加算と高速べき乗例題の説明を添付】

昨日、筆者は牛客の試合を楽しんでいた.そして、私はこのような先輩の白昼夢に出会った.

20         ，            wzc         ，        （？）。
  wzc             ，               ，             。
   wzc          ，          。
    ，wzc               x，            x2，            x3...... i          xi。
  wzc      i    ，        。          ，    9999999967     。
    :
       T，        。（1≤T≤1×103）
   T ，      x i，           ，             。
（1≤x≤10，      ，          ）
（1≤i≤1×109）

    :
  T ，      ，  xi 9999999967     。

  1
  
2
1 1000000000
2 3

  
1
8

速く問題を読み終わって、筆者の心の中はひそかに喜んで、ははは、これは1つの急速なべき乗を試験するのではありませんか?(まさかまさか、まさか、まさか本当に高速べき乗ができない人がいるのではないでしょうか---->【高速べき乗】csdnブログ)
そして、筆者は自信を持って完璧だと思っていたコードをノックした.

#include

#define ll long long
using namespace std;
ll n = 9999999967;
ll t;

ll qmi(ll x, ll i)
{
	ll ans=1;
	ll k = x%n;
	while (i)
	{
		if (i & 1)
		{
			ans = ans  *( k % n);
		}
		i >>=1;
		k = k * k%n;
	}
	return ans;
}
int main()
{
	cin >> t;
	while (t--)
	{
		ll x, i;
		cin >> x >> i;
		cout << qmi(x, i) << endl;
	}
	return 0;
}

送信!そして...wa?
ニャーニャー???まさか???型取りの部分を間違えました???
苦労して1時間後、出題者の険悪な心を見つけた...
n=9999999667、1 e 9より大きい.2つの数のnを型抜きすると最大1 e 20になる可能性がある.そして、私たちのlong long子供は光栄にも爆破しました...
ああ、どうしたんですか.どういうことですか.どうしたの?long long小朋友你hold住啊!!!!!!!!TAT
ああ、おじいさんに教えてもらいましょう.そして、筆者はおじいさんの一番長い指を背負って、解決方法を学びました.クイックプラス!
高速加算は実際には乗算であり、乗算の本質は加算であり、高速べき乗の思想を通じて高速加算のコードを簡単に書くことができることを知っています.

#include
#define ll long long
using namespace std;
const long long mod = 9999999967;

long long cheng(long long a, long long b) {
    long long res = 0;
    while (b)
    {
        if (b & 1) res = (res + a) % mod;
        b >>= 1;
        a = (a * 2) % mod;
    }
    return res;
}

long long ksm(long long a, long long b) {
    long long res = 1;
    while (b)
    {
        if (b & 1) res = cheng(res, a) % mod;
        b >>= 1;
        a = cheng(a, a) % mod;
    }
    return res;
}


int main()
{
    int t;
    cin >> t;
    while (t--) {
        long long ans;
        long long x, i;
        cin >> x >> i;
        ans = ksm(x, i);
        ans %= mod;
        cout << ans << endl;
    }
    return 0;
}

高速べき乗と同様に、高速加算もビット演算で実現し、高速加算のコードを高速べき乗に使用する必要があります.
では、次に、なぜlong long子供を爆破しなくてもいいのかを説明する必要があります.まず、2つの1 e 10の数を乗算して型modを取るのは、まず1 e 20の数字を得てから型を取るので、もちろん、私たちが1 e 20を得たとき、long longはすでに爆破しました.ビット演算で加算に変更し、2つの1 e 10の数字を加算してmodをモデリングすると、データのサイズはlong longの1 e 18以内になるに違いありません.この問題は、出題者が吐き気を催して型を取る数字を10桁に設定したためで、あなたの普通の高速べき乗をカードするためです.快速プラスと思わないと書きづらい(もちろん快速プラスは唯一の解題方法ではないが…その方法はもっと変態TATらしいので、ここで取り上げておきましょう、学びたい仲間は[_int 128_t]データ構造を見に行きます)
作者:Avalon Demerzel、勉强に励んでいるシロですが、ブログがいいと思ったら、三連にしましょう.一緒に進歩しましょう.