|

General

# Author Problem Lang Verdict Time Memory Sent Judged
55478881 Practice:
McDic
1182E - 28 GNU C++17 Accepted 31 ms 2604 KB 2019-06-12 06:15:12 2019-06-12 06:15:12
→ Source
#include <stdio.h>
#include <vector>
#include <set>
#include <map>

// Constants
typedef long long int lld;
const lld R = 1000 * 1000 * 1000 + 7; // a^(R-1) = 1 (mod R)
const lld matrixRemainder = R-1;

// Matrix class
class matrix{
public:

// Attributes
int row, col;
std::vector<std::vector<lld>> num;

// Constructor
matrix(int row, int col, int defaultValue = 0){
this->num = std::vector<std::vector<lld>>(row, std::vector<lld>(col, defaultValue));
this->row = row, this->col = col;
}
matrix(std::vector<std::vector<lld>> num){
this->num = num;
this->row = this->num.size();
this->col = this->num[0].size();
}

// Operator
matrix operator *(matrix &another){
if(this->col != another.row){
printf("Wrong size: %d*%d X %d*%d\n", this->row, this->col, another.row, another.col);
throw "Wrong size";
}
matrix newone(this->row, another.col);
for(int r=0; r<newone.row; r++) for(int c=0; c<newone.col; c++){
for(int k=0; k<this->col; k++){
newone.num[r][c] += this->num[r][k] * another.num[k][c];
newone.num[r][c] %= matrixRemainder;
}
} return newone;
}

// Power
matrix operator ^(lld x){
if(x==0){
printf("Not implemented yet.\n");
throw "Not implemented";
}
else if(x==1) return *this;
else{
matrix halfpower = (*this) ^ (x/2);
if(x%2 == 0) return halfpower * halfpower;
else return halfpower * halfpower * (*this);
}
}
};

// Prime related
const int limit = 1<<20;
bool isPrime[limit] = {false, };
std::vector<lld> primes;

// Decomposite given value to primes
std::vector<lld> primeDecomposition(lld x){
for(lld p: primes){
if(x <= 1) break;
else if(x%p == 0){
while(x%p == 0) x /= p;
}
else if(p*p > x){
break;
}
}

// Return a^x % R
lld power(lld a, lld x){
if(x==0) return 1;
lld half = power(a, x/2);
if(x%2 == 0) return half*half%R;
else return half*half%R*a%R;
}

// Main function
int main(void){

// Matrix functionality testing
//matrix a1({{1, 2}, {0, 1}}), a2({{3, 2}, {-1, 0}});
//matrix b = a1*a2;
//printf("a1*a2 = \n  %lld %lld\n  %lld %lld\n", b.num[0][0], b.num[0][1], b.num[1][0], b.num[1][1]);

// Calculate primes
for(int i=2; i<limit; i++) isPrime[i] = true;
for(int i=2; i<limit; i++) if(isPrime[i]){
primes.push_back((lld)i);
for(int j=2*i; j<limit; j+=i) isPrime[j] = false;
}

// Get input
lld n, f[4], c; scanf("%lld %lld %lld %lld %lld", &n, &f[1], &f[2], &f[3], &c);
matrix baseLogPropagate({{1, 1, 1}, {1, 0, 0}, {0, 1, 0}});
matrix totalLogPropagate = baseLogPropagate ^ (n-3);

// Calculate target primes
std::set<lld> knownprimes;
for(int i=1; i<=3; i++) for(lld p: primeDecomposition(f[i])) knownprimes.insert(p);
for(lld p: primeDecomposition(c)) knownprimes.insert(p);
//printf("Known primes: "); for(lld knownprime: knownprimes) printf("%lld, ", knownprime); printf("\n");

// Calculate c^n * f[n]'s prime count: initPrimeCount[x]: f[3-x]'s p-occurrence
std::map<lld, lld> fnPrimeCount;
for(lld p: knownprimes){
matrix initPrimeCount(3, 1);
for(int i=1; i<=3; i++){
for(lld num = f[i]; num%p == 0; num /= p) initPrimeCount.num[3-i][0]++; // f[n]
for(lld num = c; num%p == 0; num /= p) initPrimeCount.num[3-i][0] += i; // c^n
}
matrix lastPrimeCount = totalLogPropagate * initPrimeCount;
fnPrimeCount[p] = lastPrimeCount.num[0][0];
}

// Calculate answer = product(p^fnPrimeCount[p]) * c^(-n)
for(auto pinfo: fnPrimeCount){
//printf("%lld-occurrence = %lld\n", pinfo.first, pinfo.second);
}
return 0;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?