手机版企业网站,深圳比邻网站建设,wordpress 防下载,小程序报价开发题幂算.一切即1 阴阳迭变积微著#xff0c;叠浪层峦瞬息功 莫道浮生千万事#xff0c;元知万象一归宗 文章目录 快速幂原始快速幂#xff08;O(logn)#xff09;二分递归形式非递归形式 模下意义的快速幂#xff08;O(logn)#xff09;二分递归形式非递归形式 快速乘龟速… 题幂算.一切即1 阴阳迭变积微著叠浪层峦瞬息功 莫道浮生千万事元知万象一归宗 文章目录 快速幂原始快速幂O(logn)二分递归形式非递归形式 模下意义的快速幂O(logn)二分递归形式非递归形式 快速乘龟速乘O(logn)递归式非递归式 快速乘光速乘O(1) 文献参考总结 快速幂
原始快速幂O(logn)
二分递归形式
#includebits/stdc.h
using namespace std;#define ll long long ll q_pow(ll base,ll exp)
{if(exp 0) return 1;ll res q_pow(base,exp/2);if(exp 1) return res*res*base;return res*res;
}int main()
{ll a,b;cin a b; cout q_pow(a,b);
}非递归形式
#includebits/stdc.h
using namespace std;#define ll long long ll q_pow(ll base,ll exp)
{ll res 1;while(exp){if(exp 1){res res * base; }base base * base;exp 1;}return res;
}int main()
{ll a,b;cin a b; cout q_pow(a,b);
}
模下意义的快速幂O(logn) 例题 洛谷P1226 二分递归形式
#includebits/stdc.h
using namespace std;#define ll long long ll q_pow(ll base,ll exp,ll digit)
{if(exp 0) return 1;base % digit;ll res q_pow(base,exp/2,digit);if(exp 1) return (res*res)%digit*base%digit;return res*res%digit;
}int main()
{ll a,b,c;cin a b c; cout a ^ b mod c q_pow(a,b,c);
}非递归形式
#includebits/stdc.h
using namespace std;#define ll long longll q_pow(ll base,ll exp,ll digit)//一般来说digit写成mod多一点个人习惯
{base % digit;ll res 1;while(exp){if(exp 1){res res * base % digit; }base base % digit * base % digit;exp 1;}return res;
}int main()
{ll a,b,c;cin a b c; cout a ^ b mod c q_pow(a,b,c);
}快速乘
龟速乘O(logn)
递归式
#include bits/stdc.h
using namespace std;#define ll long long
const int mod 500;ll q_mul(ll a, ll b)
{if (b 0) return 0;ll res q_mul(a, b / 2);if (b 1) return (res res a) % mod;//龟速乘的目的就是为了处理大数相乘使用使用modreturn (res res) % mod;
}int main()
{ll a, b;cin a b;cout q_mul(a, b);
}非递归式
#include bits/stdc.h
using namespace std;#define ll long long
const int mod 500;ll q_mul(ll a, ll b)
{a % mod;ll res 0;while (b){if (b 1){res (res a) % mod;}a (a a) % mod;b 1;}return res;
}int main()
{ll a, b;cin a b;cout q_mul(a, b);
}快速乘光速乘O(1)
不是特别卡常数不建议使用可能会有计算错误
#include bits/stdc.h
using namespace std;#define ll long long
#define ld long double
const int mod 1e5;ll q_mul(ll a, ll b)//非压行版
{ld temp (ld)a * b / mod;ll q (ll)temp * mod;return (a * b - q mod) % mod;
}
ll q_mul(ll a, ll b)
{return (a * b - ((ll)((ld)a * b) / mod)*mod mod) % mod;
}int main()
{ll a, b;cin a b;cout q_mul(a, b);
}记忆锚点 q (ld)a * b / mod (a * b − ( ll)q * mod mod) % mod 文献参考
【OI Wiki - 快速幂】 CSDN -【谈谈知识点】快速幂龟速乘快速乘 总结
阴阳二进制的火花在递归中迭变模数宇宙的涟漪于位运算里震荡。代码中的每一个移位都是对混沌的降维打击递归栈底的return 1如同宇宙大爆炸的奇点从虚无中诞生万千可能。新手当知算法修炼是铸剑过程递归与迭代是阴阳双刃调试时的报错声恰是淬火的嘶鸣。 无论指数如何膨胀终将拆解为二进制的星辰纵使乘数浩如烟海亦可化作位运算的细沙。记住你写的不是代码而是将混沌世界重构成数学之美的炼金术。
