Modulo binomialu
Ostatnio zmodyfikowano 2017-11-13 13:53
milmega Temat założony przez niniejszego użytkownika |
Modulo binomialu » 2017-11-11 12:04:59 Muszę napisać program, który wypisze 1 jeśli n po k jest podzielne przez 3, a w przeciwnym wypadku 0. Limity to: Time: 2 s, Memory: 64 MB, (0 ≤ k ≤ n ≤ 1000000). Napisałem taki program, lecz działa tylko dla mniejszych liczb. Dla np. n=150, k=75 przekracza już unsigned long long. Zgaduję, że jest jakiś sposób na sprawdzanie czy ten binomial jest podzielny przez 3 przed obliczaniem n po k. Tylko jaki... Dziękuję za każdą podpowiedź. #include<iostream>
using namespace std;
unsigned long long Newton( unsigned int n, unsigned int k )
{
unsigned long long Wynik = 1;
for( unsigned int i = 1; i <= k; i++ )
{
Wynik = Wynik *( n - i + 1 ) / i;
}
return( unsigned long long ) Wynik;
}
int main()
{
int n, k, t;
cin >> t;
while( t-- ) {
cin >> n >> k;
unsigned long long wynik = Newton( n, k );
if( wynik % 3 == 0 ) cout << 1 << '\n';
else cout << 0 << '\n';
}
return 0;
}
|
|
Luq |
» 2017-11-11 14:19:20 |
|
milmega Temat założony przez niniejszego użytkownika |
» 2017-11-11 15:38:52 Chodzi o SIGMA[n/k] gdzie [] oznacza całkowite dzielenie? |
|
Luq |
» 2017-11-12 11:16:14 Chodzi o wykorzystanie tego wzoru z sumą do rozwiązania tego zadania. |
|
mateczek |
» 2017-11-13 13:53:57 mogę Ci zaproponować łopatologiczne rozwiązanie czy się zmieści w limicie czasu tego nie wiem kombinacje(6,4)= 6*5*3*4/1*2*3*4 gdy składowa licznika dzieli się przez "3" zwiększamy wartość o jeden gdy składowa mianownika dzieli się przez "3" zmniejszamy wartość o jeden count =0; licznik 6 count =1; //bo się dzieli mianownik 1 count =1; licznik 5 count =1; mianownik 2 count =1 licznik 3 count =2 //bo się dzieli mianownik 3 count =1 //bo się dzieli jeśli ogólna wartość będzie dodatnia >0 to całość też się dzieli #include<iostream>
using namespace std;
int Newton( unsigned int n, unsigned int k )
{
int count = 0;
for( unsigned int i = 1; i <= k; i++ )
{
int mianownik = i;
while( mianownik % 3 == 0 ) {
count--;
mianownik /= 3;
}
int licznik =( n - i + 1 );
while( licznik % 3 == 0 ) {
count++;
licznik /= 3;
}
}
return count;
}
int main()
{
int n = 6;
int k = 4;
if(( n - k ) < k ) k = n - k;
cout << Newton( n, k ) << endl;
}
|
|
| « 1 » |