Euler Projesi 250. Soru

250250

{$1^1, 2^2, 3^3, ... , 250250^{250250}$} kümesinin elemanları toplamı 250 ile bölünebilen boş olmayan altkümeleri sayısı kaçtır?
Cevabınızı en sağdaki 16 basamak olarak veriniz.

[Project Euler]
Cevap: 1425480602091519
  PYTHON: m = 250 mm = 10 ** 16 x = m * [0] for i in range(1, 250251): x[pow(i, i, m)] += 1 y = [1] + (m - 1) * [0] for i in range(m): for j in range(x[i]): y = [(y[k] + y[(k-i)%m]) % mm for k in range(m)] print(y[0] - 1) C,C++: #include <stdio.h> #include <math.h> #include <vector> #include <map> using namespace std; int powval[350250]; bool isprime(int x) { for(int i=2;i*i<=x;i++) if(x%i==0) return 0; return 1; } int findmodpow(int i,int j) { if(j==0) return 1; int tmp=findmodpow(i,j/2); if(j%2==0) return (tmp*tmp)%250; else return (tmp*tmp*((i)%250))%250; } int main() { long long int MOD=10000000000000000ll; for(int i=1;i<=250250;i++) { powval[i]=findmodpow(i,i)%250; //printf("%d %d\n",i,powval[i]); } long long int answer[251][2]; for(int j=0;j<250;j++) answer[j][0]=0; answer[0][0]=1; for(int i=1;i<=250250;i++) { for(int j=0;j<250;j++) { answer[j][1]=(answer[(j-powval[i]+250)%250][0]+answer[j][0])%MOD; } for(int j=0;j<250;j++) answer[j][0]=answer[j][1]; } printf("%lld\n",answer[0][0]-1); } MATHEMATICA: k = Table[PowerMod[i, i, 250], {i, 1, 250250}]; g2[x_] := Flatten[{Table[h2[[i + 250 - x]] + h2[[i]], {i, 1, x}], Table[h2[[i]] + h2[[i - x]], {i, x + 1, 250}]}];Timing[For[i = 1, i <= 250250, i++, h2 = g2[k[[i]]]]; h2[[1]]] JAVA: long[] mods = new long[mod]; for (int i = 1; i <= limit; i++) { int q = ((int)modpow(i,i,mod)); long[] tempmods = new long[mod]; for (int j = 0; j < mod; j++) { int qj = (q+j)%mod; long tempval = mods[qj] + mods[j]; if (tempval > sizelimit) tempval -= sizelimit; tempmods[qj] = tempval; } mods = tempmods; mods[q]++; // This is why I didn't need to set // mods[0]=1 at the beginning }