Cześć ktoś wie jak zapisać dzielenie modulo w rekurencji?
Zadanie: a∗b mod m
Mam zwykłe:
#include<iostream>
using namespace std;
int main()
{
long long int n,a,c;
cin>>a>>n>>c;
cout<<n%c*a%c;
return 0;
}
C++ - Rejestracja:prawie 8 lat
- Ostatnio:ponad 3 lata
- Postów:318
0
A czasami nie chodzi tu o wyliczenie reszty z dzielenia za pomocą rekurencji zamiast %? Coś w stylu - https://math.stackexchange.com/questions/580907/recursive-function-mod-5
- Rejestracja:ponad 6 lat
- Ostatnio:ponad 5 lat
- Postów:83
0
Dokładnie takie zadanie:
http://solve.edu.pl/contests/download_desc/1998
edytowany 1x, ostatnio: flowCRANE
- Rejestracja:około 6 lat
- Ostatnio:około 6 lat
- Postów:6
0
Takie coś ci wyrzeźbiłem na szybko.
Twoim zadaniem jest obliczenie modulo z recmod() ...
using std::cin;
using std::cout;
long long recmod();
int counter=0;
int main() {
cout<< recmod();
return 0;
}
long long recmod() {
long long a=1;
while (counter<2) {
cout<<"Podaj "<<counter+1<<" element: ";
cin>>a;
counter++;
cout<<"\n";
a*=recmod();
}
return a;
}
i wyczyszczenie ładnie tego kodu.
edytowany 3x, ostatnio: Apurimac
To mnoży dwie liczby :-D
- Rejestracja:prawie 8 lat
- Ostatnio:ponad 3 lata
- Postów:318
0
Moja próba na podstawie zalinkowanego wcześniej przykładu:
#include <iostream>
#include <cmath>
int recmod(int a, int b, int m ) {
if (a*b < m) {
return a*b;
} else {
if (a>b) {
return abs(recmod(a-m, b, m));
}
else {
return abs(recmod(a,b-m,m));
}
}
}
int main() {
std::cout << recmod(2,3, 4);
std::cout<<recmod(2,21,10);
}
Edit:
Dodałem abs na wypadek(m>a || m >b).
edytowany 4x, ostatnio: Serechiel
- Rejestracja:ponad 6 lat
- Ostatnio:ponad 5 lat
- Postów:83
0
Taki kod ale sprawdzaczka pokazuje błędne odpowiedzi :-(
#include <iostream>
#include <cmath>
long long int recmod(int a, int b, int m ) {
if (a*b < m) {
return a*b;
} else {
if (a>b) {
return abs(recmod(a-m, b, m));
}
else {
return abs(recmod(a,b-m,m));
}
}
}
int main()
{
long long int a;
long long int b;
long long int m;
std::cin>>a;
std:: cin>>b;
std::cin>>m;
std:: cout << recmod(a,b,m);
}
Widocznie sprawdzarka chce też dobrych wyników gdy w
a * b jest overflow.
ale co poprawić ?
10^18 * 10^18 przekracza możliwości long long int(nawet unsigned) - http://www.cplusplus.com/reference/climits/
Coś mi mówi, że trzeba pokombinować z a*b
- Rejestracja:prawie 8 lat
- Ostatnio:ponad 3 lata
- Postów:318
0
Nie wnikam, ale coś czuje, że czepia się o
if (a*b <m)
Jak wiadomo z lekcji matematyki jeżeli a x b < m to a < m/b
if(a < m/b)
lub
if (b < m/a)
czepiać się nie powinno, bo nijak dopuszczalnych maksymalnych wartości nie przekroczy. Dodałbym też przypadek a x b = m (a = m/b), który jak wiadomo ma zwrócić 0.
Edit:
Na moje wypociny nie zwracajcie uwagi. Znalazłem przypadek. który dla a<10, b<10 i m<10 daje zły wynik.
edytowany 1x, ostatnio: Serechiel
- Rejestracja:około 8 lat
- Ostatnio:około 8 godzin
- Postów:4897
0
Jest to jakiś postęp, ale dalej może być overflow w (a % m) * (b % m):
#include <iostream>
#include <climits>
#define ull unsigned long long int
ull recmod(ull a, ull b, ull m ) {
if (a <= LONG_LONG_MAX / b){
if (a*b < m) {
return a*b;
} else {
if (a>b) {
return recmod(a-m, b, m);
}
else {
return recmod(a,b-m,m);
}
}
}
else {
return ((a % m) * (b % m)) % m;
}
}
int main() {
std::cout << recmod(13, 5, 4) << "\n";
}
Zobacz pozostałe 3 komentarze
Co to znaczy?
...że robi niedozwoloną operację albo wychodzi poza tablicę na przykład, albo program używa niedozwolonych funkcji.
Mam to w jednym teście.
Najśmieszniejsze, że kod z pierwszego postu ma najwięcej zaliczonych testów :-)
To co, nie można używać
climits?
Tego co nie można używać nie wiem.
OGRANICZENIA:
0<=a<=10^18, 0<=b <=10^18, 1<=m<=10^18.
Dla testu: 0 0 1<br />
Floating point exception (core dumped)
- Rejestracja:prawie 8 lat
- Ostatnio:ponad 3 lata
- Postów:318
1
Przy małych liczbach pewnie by wystarczyło takie coś:
#include <iostream>
int recmod(int a, int b, int m ) {
if (a*b < m) {
return a*b;
}
else {
return recmod(1, a*b-m, m);
}
}
int main() {
std::cout << recmod(5,4,7);
}
Przy większych - axb na 99.99% da overflow.
Chyba znalazłem:
https://www.geeksforgeeks.org/how-to-avoid-overflow-in-modular-multiplication/
edytowany 2x, ostatnio: flowCRANE
To jest dobry algorytm. A tutaj dobry sposób na pozbycie się problemów z ograniczeniami: https://www.geeksforgeeks.org/multiply-large-numbers-represented-as-strings/
to nie jest dobry algorytm! https://eduinf.waw.pl/inf/alg/001_search/0017.php#A1
- Rejestracja:ponad 6 lat
- Ostatnio:ponad 5 lat
- Postów:83
0
Rozwiązanie.
Taki kod napisałem:
#include <iostream>
using namespace std;
long long p = 0, n = 0;
long long m(long long a, long long b, long long c)
{
if (b == 0) {
return 0;
}
if (b == 1) {
return a % c;
}
else {
p = b / 2;
n = m(a, p, c);
if (b % 2 == 0) {
return (n + n) % c;
}
else {
return (n + a + n) % c;
}
}
}
int main()
{
long long a, b, c;
cin >> a >> b >> c;
if (c == 1 || a == 0 || b == 0) {
cout << 0;
}
else
cout << m(a, b, c) % c;
}
%?