x nod 1000 != 3 ostatnie cyfry x (?!)

[KaMyLuS]

<-- pracuje nad tym zadaniem, programuję w c++. Mój program działający na zasadzie licz wynik ze schematu Hornera, po drodze wszystko moduluj przez 1000, dostaje tylko 80/100 pkt, czyli nie przechodzi 2och testow. Jako ze sa to duze testy, to nie moge ich recznie zbadac... W zwiazku z tym nasuwa mi sie pytanie: czy jest mozliwe, by reszta z dzielenia wartosci wielomianu przez 1000 byla czyms innym niz 3ma ostatnimi cyframi tejże wartosci? Jesli tak, to jak sobie z tym poradzic, zeby w programie bylo wszystko OK?

[frej]

To może zrób tak:
\(\displaystyle{ W(x)=a_0+x\left( a_1 + x\left( a_2 + x \left( \ldots a_{n-1}+a_n x \right) \ldots \right) \right)}\)
Czyli masz liniową złożoność od stopnia wielomianu.

Zaznaczam, że moja wiedza informatyczna jest nikła, więc ten pomysł może być nieefektywny...-- 6 sierpnia 2009, 17:58 --Oczywiście wszytko \(\displaystyle{ \pmod{1000}}\)

[Zordon]

przypuszczam, ze może być kłopot z ujemnymi wartościami, np. jeśli W(x)=-1, to ty zwracasz 999.

albo zle dopelniasz zerami. A wyskakuje zla odpowiedz, czy czas?

[KaMyLuS]

@frej:
Tak własnie robie, to jest schemat Hornera, i wszystko mod 1000
@Zordon:
C++ dla ujemnych daje ujemny mod, tzn np. (-7)%10 = -7. Zerami wszystko na glanc dopelniam, czasy mam super, tylko dla 2och testow mam zle odp, a ze to jest na mainie to widze jaki ja mam wynik, a jaki jest wzorcowy. Z tymze jak mowilem, te 2 testy sa duze wiec recznie ich ni przeanalizuje... A kod programu wyglada tak:

Kod: Zaznacz cały

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;

#define VAR(a,b) __typeof (b) a = b
#define REP(i,n) for (int _n=(n), i=0; i<_n; ++i)
#define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i)
#define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i)
#define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i)
#define abs(a) ((a)<0 ? -(a) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef long long int ll;
typedef long double ld;

int s;
ll x, a[20010], wyn;

int main()
{
    scanf("%d %lld", &s, &x);
    x %= 1000;
    REP(i, s) scanf("%lld", &a[i]); ;     
    wyn = a[0]%1000;
    FOR(i, 1, s-1) wyn = (a[i]%1000 + (wyn*x)%1000)%1000;
    printf("%0*lld
", 3, abs(wyn%1000));
    system("pause");
    return 0;
}

[Zordon]

nikt Ci nie będzi kodu naprawiał, tymbardziej z makrami. Sprawdź np. co wyskakuje dla wielomianu \(\displaystyle{ -999x^2-3x+10}\), \(\displaystyle{ x=1}\)

i przede wszystkim wywal system("pause");

[KaMyLuS]

Heh to modulo jakies wredne jest przez te ujemne liczby :/ Juz widze co sie dzieje (najpierw mam -3-999=-1002 -1002 mod 1000 = -2, no a z tego raczej 992 (ktore ma wyjsc) nie zrobie :/). Wie ktos moze co tu powinienem zrobic zeby modulo dobre bylo?