- 浏览: 2000 次
最新评论
文章列表
题目:求 a^n % p。
分析:a^n = a^(2^0 * n[0] + 2^1 * n[1] + 2^2 * n[2] + ... + 2^(t-1) * n[t-1])
= (a^(2^0))^n[0] * (a^(2^1))^n[1] * (a^(2^2))^n[2] * ... * (a^(2^(t-1)))^n[t-1]
其中,t = log(n),n[i] = 0或1
代码:
public class OJ {
public static void main(String[] args) {
...
int add(int a, int b)
{
int c;
while (0 != b) {
c = a ^ b;
b = (a & b) << 1;
a = c;
}
return a;
}
方法一:
void swap(int& a, int& b)
{
a = a + b;
b = a - b;
a = a - b;
}
方法二:
void swap(int& a, int& b)
{
a ^= b;
b ^= a;
a ^= b;
}