| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 9814 |
2014-09-28T09:55:26 Z |
maniac |
Phibonacci (kriii2_P) |
C++ |
|
0 ms |
1092 KB |
#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 && m == 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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1092 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
