12318 - Digital Roulette

[Amoeba]

I think. my logic is correct.

but i got a WA.

is there mistake in my code?

here my code.

Code: Select all

#include "stdio.h"
#include "memory.h"
#include "algorithm"
#include "math.h"

#define MAX 100001

using namespace std;

int main()
{
	int  poly[11];
	int  answer[MAX];
	int  size, loop, degree, cnt;
	long long temp;

	while(1)
	{
		scanf("%d %d", &size, &loop);

		if(size == 0 && loop == 0)
			break;

		scanf("%d", &degree);

		cnt = 1;
		memset(answer, -1, sizeof(answer));
		memset(poly, 0, sizeof(poly));

		for(int i=0; i<=degree; i++)
			scanf("%d", &poly[i]);

		for(int i=0; i<=loop; i++)
		{
			answer[i] = poly[0];
			temp = i;

			for(int j=1; j<=degree; j++)
			{
				if(poly[j] != 0)
				{
					temp = pow((long double)i, j);
					temp %= (size+1);	
					poly[j] %= (size+1);
					answer[i] += poly[j] * temp;

					if(answer[i] > size)
						answer[i] %= size+1;
				}
			}
		}

		sort(answer, answer+loop+1);

		for(int i=0; i<loop; i++)
		{
			if(answer[i] != answer[i+1])
				cnt++;
		}
		printf("%d\n", cnt);
	}	
	return 0;
}

ps.is there mistake related number range in my code?

help me plz.

[seidan]

the last result of the examples is 10 and in your code is 11??

Sorry for my english

[outsbook]

do not use pow() method for calculating x^k
make a pow method

Code: Select all

long pow(long x, int k)
----if k==0 then return 1
----powval = x%(N+1)
----for i=1 to k-1 
------powval *= x
------powval  %= (N+1)

I think now the problem is very easy

[Amoeba]

I had changed pow method many times

but i still got a WA

Code: Select all

#include "stdio.h"
#include "memory.h"
#include "algorithm"

#define MAX 100001

using namespace std;

long long power(long long x, int k, int size)
{
	long long powval;

	if( k==0)
		return 1;
	powval = x%(size+1);

	for( int i=1; i<= k-1; i++) 
	{	
		powval *= x;
		powval  %= (size+1);
	}
	return powval;
	
	/*x %= (size+1);

	if(k == 0)
	return 1;
	else if((k%2) == 0)
	return power(x*x, k/2, size);
	else
	return x*power(x*x, (k-1)/2, size);*/
}

int main()
{
	int  poly[11];
	int answer[MAX];
	int loop, degree, cnt, size;
	long long temp;

	while(1)
	{
		scanf("%d %d", &size, &loop);

		if(size == 0 && loop == 0)
			break;

		scanf("%d", &degree);

		cnt = 1;
		memset(answer, -1, sizeof(answer));
		memset(poly, 0, sizeof(poly));

		for(int i=0; i<=degree; i++)
			scanf("%d", &poly[i]);

		for(int i=0; i<=loop; i++)
		{
			answer[i] = poly[0];
			temp = i;

			for(int j=1; j<=degree; j++)
			{
				if(poly[j] != 0)
				{
					temp = power(i, j, size);
					answer[i] = temp * poly[j];

					if(answer[i] > size)
						answer[i] %= size+1;
				}
			}
		}

		sort(answer, answer+loop+1);

		for(int i=0; i<loop; i++)
			if(answer[i] != answer[i+1])
				cnt++;

		printf("%d\n", cnt);
	}   
	return 0;
}

i dno't know where is mistake T T

help me.

[Amoeba]

one more question

shuld i use long long or long long int? behalf of int??

[Amoeba]

Now I got a AC.

thx^^

I changed pow method.

Have a nice day~