1 条题解

  • 1
    @ 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

信息

难度
9
分类
数论 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者