题意：给出了一段伪代码。分析得知其实就是f[1]= a,f[2] = b,f[n]=f[n-1] * f[n-2]
思路：一眼题，和hdu4549很类似hdu4549解题报告
不同的是这道题中p不一定是质数（其实不是也无所谓啊…hdu4549只不过是因为1E9+7是指数，又用费马小定理化简了一下,这道理%phi(p)即可）
还有这道题让我知道了
首先我们知道指数循环节公式，也就是所谓的降幂公式为：a^x = a^(x mod phi(c)+phi(c)) (mod c) x>=phi(c)，（
ps:后面的限制条件，在x<phi(c)的时候，该式子依然正确，只不过增加了运算复杂度。。。？ 存疑）
括号里的话是错误的。只有当x<phi(c)的时候，这个公式才成立。
这道题就是反例，不加判断会wa。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 |
/* *********************************************** Author :111qqz Created Time :Sun 30 Oct 2016 11:46:33 PM CST File Name :code/hdu/3221.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; LL a,b,p,n; LL mod; LL euler( LL x) { LL ret = 1; for ( LL i = 2 ; i*i <= x; i++) { if (x%i==0) { x/=i; ret*=(i-1); while (x%i==0) { x/=i; ret*=i; } } } if (x>1) ret*=(x-1); return ret; } struct Mat { LL mat[2][2]; void clear() { ms(mat,0); } }M,M1; Mat operator * (Mat a,Mat b) { Mat res; res.clear(); for ( int i = 0 ; i < 2 ; i++) for ( int j = 0 ; j < 2 ; j++) for ( int k = 0 ; k < 2 ; k++) { res.mat[i][j] = (res.mat[i][j] + a.mat[i][k]*b.mat[k][j]); if (res.mat[i][j]>=mod) res.mat[i][j] = res.mat[i][j] % mod + mod; } return res; } Mat operator ^ (Mat a,LL b) { Mat res; res.clear(); for ( int i = 0 ; i < 2 ; i++) res.mat[i][i] = 1; while (b>0) { if (b&1) res = res * a; b = b >> 1LL; a = a * a; } return res; } void init() { M.clear(); M.mat[0][1] = M.mat[1][0] = M.mat[1][1] = 1; M1.clear(); M1.mat[0][0] = 0 ; M1.mat[1][0] = 1; } LL ksm( LL a,LL b,LL k) { LL res = 1LL; while (b>0) { if (b&1) res = (res * a) % k; b = b >> 1LL; a = ( a * a ) % k; } return res; } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif int T; int cas = 0 ; cin>>T; while (T--) { scanf("%lld%lld%lld%lld",&a,&b,&p,&n); printf("Case #%d: ",++cas); if (n==1) { printf("%lld\n",a%p); continue; } if (n==2) { printf("%lld\n",b%p); continue; } init(); mod = euler(p); Mat ans; ans.clear(); ans = (M^(n-2))*M1; LL x = ans.mat[0][0]; LL y = ans.mat[1][0]; LL ret = ksm(a,x,p)*ksm(b,y,p)%p; printf("%lld\n",ret); // printf("Case #%d: %lld\n",++cas,ret); } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人！