1 条题解
-
1Root (sky1231) LV 8 MOD @ 2018-05-09 17:01:33
#include <cmath> #include <ctime> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #include <vector> #include <deque> #include <set> #include <limits> #include <string> #include <sstream> using namespace std; namespace dts { typedef long long ll; ll n,t,key; ll qp(ll x,ll y,ll key) { ll ans=1; for (ll i=x,j=y;j>0;i=(i*i)%key,j/=2) if (j&1) ans=(ans*i)%key; return ans; } ll ny(ll x,ll key) { if (x==1) return 1; else return -(key/x)*ny(key%x,key)%key; } void main() { while (~scanf("%lld%lld%lld",&n,&t,&key)) { ll p=ny(3,key); if (p<0) p+=((key-p)/key)*key; ll f=qp(2,n,key)+2*((n&1)?-1:1),g=2*qp(2,n,key)-2*((n&1)?-1:1); if (f<0) f+=((key-f)/key)*key; if (g<0) g+=((key-g)/key)*key; f=(f*p)%key,g=(g*p)%key; //f(x)=(1/3)*2^x+(2/3)*(-1)^x //g(x)=(2/3)*2^x-(2/3)*(-1)^x t%=key; printf("%lld %lld\n",(f*t)%key,(g*t)%key); } } }; int main() { dts::main(); }
- 1