marynarz 2

// gra_marynarz.cpp : Defines the entry point for the console application.
//

#include <cstdio>
#include <cstdlib>
#include <algorithm>


  int *trafien;
  int *ntrafien;
  int *cumsum;

void graj3 (int graczy, int palcow, int modulo)
{


    trafien[0]=1;
    for (int i=1;i<graczy;i++)
        trafien[i]=0;

    for (int gr=0;gr<graczy;gr++)
    {

        for (int g=0;g<graczy;g++)
        {
            ntrafien[g] = 0;
        }
        cumsum[0]=trafien[0];
        for (int g=1;g<graczy+palcow+1;g++)
        {
            cumsum[g] = cumsum[g-1]+trafien[g % graczy];
        }


        for (int g=0;g<graczy;g++)
        {
            ntrafien[g] = (cumsum[g+palcow] - cumsum[g])%modulo;
        }
        std::swap(trafien,ntrafien);
    }

    //printf ("\n graczy %d palcow %d\n",graczy,palcow);
    //for (int gr=0;gr<graczy;gr++)
    //{
    //  printf("%lld\n ",trafien[gr]);
    //}

      int suma=0;
    for (int gr=1;gr<graczy;gr++)
    {
        if (trafien[gr-1]!=trafien[gr]) suma=1;
    }
    if (suma==0)printf ("%d %d\n" ,graczy,palcow);

}

int modpower(int x,int n, int m )
{// x^n mod m
    if (n==0) return 1;
    if (n%2==1) return (x*modpower(x,n-1,m))%m;
    else
    {
        int a = modpower(x,n/2,m);
        return (a*a)%m;
    }
}


int main()
{
    const int max_graczy=2000;
    const int max_palcow=2000;

    trafien = new    int[max_graczy];
    ntrafien = new    int[max_graczy];
    cumsum = new   int[max_graczy+max_palcow+1];

    int procent=0;
    for (int graczy = 2;graczy<max_graczy;graczy++)
    {
        if (procent*max_graczy<=graczy*1000) { printf("%.2lf%%.\n",((double)procent++/10));};

        for (int palcow = 2;palcow<max_palcow;palcow++)
            if ((modpower(palcow,graczy,graczy)==0) && (palcow%graczy!=0))
                // czy p^g / g = naturalna <=> p^g =  0 (mod g) oraz czy nie trywialne
                graj3(graczy,palcow, 9973); //9973 to jakaś liczba pierwsza
    }

    return 0;
}