湖南大学第十五届程序设计竞赛（重现赛) B题

原题链接：Kuangyeye's Resistance

Kuangyeye is a dalao of the ACM team of Hunan University. As a student majoring in communication engineering, he must learn how to analyze various circuits. One day, when he was in class, the teacher was explaining a circuit，but he was too tired to listen to his teacher and fell asleep. When he woke up, he found the teacher had drawn some resistors on the blackboard as shown in the picture below. And the homework is to calculate the equivalent resistance of the n-level network. The resistance of each resistor in the figure is R. Kuangyeye has no idea about that.
Please help pathetic Kuangyeye to solve this problem. If the answer is \frac{a}{b}
, you can just output a\times b^{-1} module P, where P is a prime.

输入描述:

The input only one test cases, which consists of three integers representing n, R, and P.

输出描述:

Output the resistance value described above.

思路：

• 模拟，从右边开始每一个环看成一个等效电阻，然后往左边递推
• 分数取余，a^{p-1}modp=1modp，
  两边乘以一个a^{-1}得：a^{p-2}modp = a^{-1}modp，
  所以 \frac{a}{b}modp=a\times b^{p-2}modp

https://blog.csdn.net/godleaf/article/details/79844074

代码：

#include<bits/stdc++.h>

using namespace std;

long long n, r, p;
struct dou {
	long long m;
	long long s;
}ans;

long long fast_mod(long long a, long long b) {
	long long r = 1;
	a %= p;
	while (b) {
		if (b & 1) r = (r*a) % p;
		a = (a*a) % p;
		b >>= 1;
	}
	return r;
}

long long qumod(const dou & du) {
	return ((du.s%p)*(fast_mod(du.m, p - 2))) % p;
}

void chuan() {
	ans.s += 2 * ans.m;
	ans.m += ans.s;
	ans.s = qumod(ans);
	ans.m = 1;
}


int main() {
	cin >> n >> r >> p;
	ans.m = 1;
	ans.s = 1;
	for (long long i = 1; i<n; ++i) {
		chuan();
	}
	cout << ((r%p)*qumod(ans))%p << endl;
}