HDU4565-So Easy!(共轭運用+矩陣快速冪)

HDU4565-So Easy!(共轭運用+矩陣快速冪)

題目鏈接

題意：

求解

思路：

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPGgzPrzHPG5vYnI+KGEmIzQzO2KhzCluPC9ub2JyPs6qPG5vYnI+QW48L25vYnI+o6zF5M/uPC9oMz4KPGgzPjxub2JyPkNuPUFuJiM0MztCbj0oYSYjNDM7YqHMKW4mIzQzOyhhP2KhzCluPC9ub2JyPjwvaDM+CjxoMz7Bvc/ux6G6w7my6e6jrMv50tQ8bm9icj5Dbjwvbm9icj7Kx9X7yv2ho9PWuPm+3c/e1sbM9bz+PC9oMz4KPGgzPjxub2JyPihhPzEpMjxiPGEyPzA8YT9iocw8MT8wPChhP2KhzCluPDE/Qm48MTwvbm9icj48L2gzPgo8aDM+0rK+zcrHy7U8bm9icj5Dbj0/QW4/PC9ub2JyPjwvaDM+CjxoMz48bm9icj5Tbj0oQ24pJW08L25vYnI+PC9oMz4KPGgzPsfzPG5vYnI+Q248L25vYnI+tcS3vbeoyse13c3GoaMKILbUPG5vYnI+Q248L25vYnI+s8vS1Dxub2JyPihhJiM0MztiocwpJiM0MzsoYT9iocwpPC9ub2JyPjwvaDM+CjxoMz48bm9icj48L25vYnI+PGJyPgo8L2gzPgo8aDM+09rKxzwvaDM+CjxoMz48bm9icj5DbiYjNDM7MT0yYUNuPyhhMj9iKUNuPzE8L25vYnI+PC9oMz4KPGgzPrDR1eK49rXdzcbKvdC0s8m+2NXz0M7KvTwvaDM+CjxoMz48bm9icj5bQ24mIzQzOzFDbl09WzJhMT8oYTI/YikwXVtDbkNuPzFdPC9ub2JyPjwvaDM+CjxoMz7T2srHvs2/ydLU08O+2NXzv+zL2cPdwLTX9sHLPC9oMz4KPGgzPjxub2JyPltDbiYjNDM7MUNuXT1bMmExPyhhMj9iKTBdbltDMUMwXTwvbm9icj48L2gzPgo8YnI+CjxwPjwvcD4KPHA+uavKvc3GtbnBtL3TPGJyPgo8L3A+CjxwPjxicj4KPC9wPgo8cD60+sLro7o8YnI+CjwvcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#include #include #include #include #include using namespace std; typedef long long ll; //typedef __int64 ll; ll a, b, n, m; struct mat{ ll s[2][2]; mat() { memset(s, 0, sizeof(s)); } mat operator * (const mat& c) { mat ans; memset(ans.s, 0, sizeof(ans.s)); for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) ans.s[i][j] = (s[i][0] * c.s[0][j] + s[i][1] * c.s[1][j]) % m; return ans; } void put() { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) printf("%lld ", s[i][j]); printf("\n"); } } }c; void init() { c.s[0][0] = 2 * a; c.s[0][1] = b - a * a; c.s[1][0] = 1; c.s[1][1] = 0; } mat pow_mod(ll k) { if (k == 1) return c; mat a = pow_mod(k / 2); mat ans = a * a; if (k % 2) ans = ans * c; return ans; } int main() { while (scanf("%lld%lld%lld%lld", &a, &b, &n, &m) != EOF) { init(); ll s1, s2; s1 = (a * 2) % m; double t = pow(a + sqrt((double)b), 2); s2 = (ll)ceil(t) % m; if (n == 1) printf("%lld\n", s1); else if (n == 2) printf("%lld\n", s2); else { mat ans = pow_mod(n - 2); ll a = (((ans.s[0][0] * s2 % m ) + m) % m + ((ans.s[0][1] * s1 % m ) + m)% m); printf("%lld\n", a % m); } } return 0; }