제출 #9813

#제출 시각아이디문제언어결과실행 시간메모리
9813maniacPhibonacci (kriii2_P)C++98
1 / 4
0 ms1092 KiB
#include <stdio.h> #include <string.h> #include <algorithm> #define SIZE 1000 using namespace std; //Addition void add(char *a, char *b, char *r, int lenA, int lenB, int &lenR){ reverse(a,a+lenA); reverse(b,b+lenB); int x,y,i,j,carry; for(i=j=lenR=carry=0;i<lenA || j<lenB || carry; i++,j++,lenR++){ x = (i<lenA)?a[i]-'0':0; y = (j<lenB)?b[j]-'0':0; r[lenR] = (x+y+carry)%10+'0'; //Here M =10 is base. carry = (x+y+carry)/10; //We can use any base } r[lenR] = 0; reverse(r,r+lenR); } //Subtraction with sign handling a>b or b>a int com(char *a, char *b){ int lenA = strlen(a); int lenB = strlen(b); if(lenA>lenB)return 1; else if(lenA<lenB)return 2; else { int i; for(i=0;i<lenA;i++){ if(a[i]>b[i])return 1; if(a[i]<b[i])return 2; } } return 0; } void sub(char *a, char *b, char *r, int lenA, int lenB, int &lenR){ bool flag = true; char temp[SIZE]; int t; if(com(a,b)==2){ strcpy(temp,a); strcpy(a,b); strcpy(b,temp); t = lenA; lenA = lenB; lenB = t; flag = false; } else if(com(a,b)==0){ strcpy(r,"0"); return; } reverse(a,a+lenA); reverse(b,b+lenB); int x,y,i,j,carry; for(i=j=lenR=carry=0;j<lenB || i<lenA || carry; i++,j++,lenR++){ x = (i<lenA)?a[i]-'0':0; y = (j<lenB)?b[j]-'0':0; y += carry; if(y>x){ r[lenR] = (10+x-y)%10+'0'; carry = (10+x)/10; } else { r[lenR] = (x-y)%10+'0'; //Here M =10 is base. carry = x/10; //We can use any base } } while(r[lenR-1]=='0')lenR--; if(!flag)r[lenR++] = '-'; r[lenR] = 0; reverse(r,r+lenR); reverse(a,a+lenA); } //Multiplication void multiply(char *a, char *r, int lenA, int &lenR, int m) { reverse(a,a+lenA); int x = 0, i = 0, carry = 0; for(i=lenR=carry=0;i<lenA || carry; i++,lenR++){ x = (i<lenA)?a[i]-'0':0; r[lenR] = (x*m+carry)%10+'0'; //Here M =10 is base. carry = (x*m+carry)/10; //We can use any base } r[lenR] = 0; reverse(r,r+lenR); reverse(a,a+lenA); } void multiply(char *a, char *b, char *r, int lenA, int lenB, int &lenR) { for (int j = 0; j < lenB; j++) { char tmp[SIZE] = {}, tmp2[SIZE] = {}; int tmpLen = 0, tmp2Len = 0; multiply(a, tmp, lenA, tmpLen, b[j] - '0'); for (int k = tmpLen; k < (lenB-1-j)+tmpLen; k++) tmp[k] = '0'; tmpLen += (lenB-1-j); tmp[tmpLen] = 0; //printf("(%s*%d=%s)\n", a, b[j]-'0', tmp); add(tmp, r, tmp2, tmpLen, lenR, tmp2Len); strcpy(r, tmp2); lenR = strlen(r); } } //Division void div(char *a,int lenA, char *r, int& k, int m){ int mod=0; k=0; int i; for(i=0;i<lenA;i++){ r[k++] = ((mod*10+a[i]-'0')/m)+'0'; mod = ((mod*10+a[i]-'0')%m); } r[k] = 0; i = 0; int j = 0; while(r[i]=='0')i++; while (r[k-1] < '0' || r[k-1] > '9') --k; for(;i<k;i++,j++)r[j] = r[i]; r[j]=0; } //Mod int mod(char *a, int lenA, int m){ int i,mod = 0; for(i=0;i<lenA;i++){ mod = (mod*10+a[i]-'0')%m; } return mod; } //Big Integer POWER a^b SIZE=1000000 void power(char *a, char *result, int lenA, int &lenR,int b){ int index,x,i,carry;; long long int m = atoll(a); for(index = 0;index<b-1;index++){ reverse(a,a+lenA); for(i=lenR=carry=0;i<lenA || carry; i++,lenR++){ x = (i<lenA)?a[i]-'0':0; result[lenR] = (x*m+carry)%10+'0'; //Here M =10 is base. carry = (x*m+carry)/10; //We can use any base } result[lenR] = 0; reverse(result,result+lenR); strcpy(a,result); lenA = strlen(a); } } const long long MOD(1000000007); typedef struct matrix{ long long d[2][2]; }Matrix; Matrix F={1, 1, 1, 0}; Matrix m_Mul(Matrix A, Matrix B){ Matrix C; C.d[0][0]=(A.d[0][0]*B.d[0][0]+A.d[0][1]*B.d[1][0])%MOD; C.d[0][1]=(A.d[0][0]*B.d[1][0]+A.d[0][1]*B.d[1][1])%MOD; C.d[1][0]=(A.d[1][0]*B.d[0][0]+A.d[1][1]*B.d[1][0])%MOD; C.d[1][1]=(A.d[1][0]*B.d[1][0]+A.d[1][1]*B.d[1][1])%MOD; return C; } Matrix _m_Power(Matrix A, long long n){ Matrix Exp = A, Ret = {1, 0, 0, 1}; while (n > 0) { if (n % 2) Ret = m_Mul(Ret, Exp); n /= 2; Exp = m_Mul(Exp, Exp); } return Ret; } Matrix m_Power(Matrix A, char* n, int nLen) { Matrix Exp = A, Ret = {1, 0, 0, 1}; while (nLen > 1 || n[nLen-1] > '0') { char tmpN[SIZE] = ""; int tmpLen = 0; /* for (int i = 0; i < nLen; i++) printf("%c", n[i]); printf("[Parity:%d=%d%2]len:%d\n", (n[nLen-1]-'0')%2, n[nLen-1]-'0', nLen); getchar(); */ if ((n[nLen-1] - '0') % 2) Ret = m_Mul(Ret, Exp); div(n, nLen, tmpN, tmpLen, 2); strcpy(n, tmpN); nLen = strlen(tmpN); Exp = m_Mul(Exp, Exp); } return Ret; } int main(void) { char a[SIZE], b[SIZE], c[SIZE], one[SIZE] = "1"; scanf("%s%s", a, c); int lenA = strlen(a); int lenB = strlen(b); int lenC = strlen(c); int lenO = 1; long long n = atoll(a), m = atoll(c); if (n == 0 || m == 0) { puts("0 1"); return 0; } else if (n == 1) { puts("1 0"); return 0; } Matrix A={1, 1, 1, 0}, B={1, 1, 1, 0}; multiply(a, c, b, lenA, lenC, lenB); //printf("%s*%s=%s(%d)", a, c, b, lenB);puts(""); strcpy(a, b); lenA = lenB; A=m_Power(A, b, lenB); sub(a, one, c, lenA, lenO, lenC); B=m_Power(B, c, lenC); printf("%lld %lld\n", A.d[0][1], B.d[0][1]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...