Polynomial

gistfile1.c

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

long long powSafe(
	long base,
	int exponent,
	long module
) {
	long long result = 1;
	int i;
	for (i = 0; i < exponent; i++) {
		result = (result * base) % module;
	}

	return result;
}

long long polyF(
	long x,
	long m,
	long coeffs[],
	int n
) {
	// loop through all coefficients, adding them up
	long long total = 0;
	int i;
	for (i = n; i >= 0; i--) {
		if (i > 0)
			total += (powSafe(x, i, m) * coeffs[i]) % m;
		else
			total += coeffs[i] % m;
	}

	return total % m;
}

int main() {
	FILE *fileI = fopen("poly.in", "r");
	FILE *fileO = fopen("poly.out", "w+");

	// Read the the first line
	// n - degree of the polynomial, range [0, 1000]
	// k - number of argument values to evaluate, range [0, 1000]
	int n, k;
	fscanf(fileI, "%d %d", &n, &k);	
	//printf("n=[%d], k=[%d]\n", n, k);

	// Read the second line
	// Number of arguments to be read - n+1
	// coeff - coefficient of the polynomial, range [0, 10^9]
	int i;
	long coeff, coeffs[n+1];
	for (i = 0; i < (n+1); i++) {
		fscanf(fileI, "%ld", &coeff);
		coeffs[i] = coeff;
		//printf("%ld ", coeff);
	}
	//printf("\n");

	// Read the rest of the document
	// Number of lines to be read - k
	// x - polynomial variable
	// m - mod value
	int line;
	long x, m;
	long long polyValue;
	for (line = 0; line < k; line++) {
		fscanf(fileI, "%ld %ld", &x, &m);
		polyValue = polyF(x, m, coeffs, n);
		fprintf(fileO, "%lld\n", polyValue);
		//printf("x=[%ld], m=[%ld], value=%lld\n", x, m, polyValue);
	}

	return 0;
}