Main - dzielniki liczby

0

Mam problem z jednym zadaniem z main'a http://main.edu.pl/pl/user.ph[...]ask&task=dzie&con=PAS
chce to zrobić w c++ . Za bruta dali mi 87 pkt jednakże chce mieć 100 , w necie szukałem gotowców i podpowiedzi jednakże nigdzie po wysłaniu nie było 100 ani nawet 87 :D .
Proszę o pomoc , najlepiej o gotowca do przeanalizowania i jeszcze czy mógłby mi ktoś wytłumaczyć czemu niektórzy stosują w warunku akurat pierwiastek z liczby n i dlaczego to jest szybsze ???

0

dzielniki występują parami, jeden jest mniejszy od pierwiastka, odpowiadający mu jest większy
jak znajdziesz jeden to od razu masz drugi do pary
uwaga na kwadraty np. 16
połącz w pary dzielniki 12, zrób to samo dla 16

0
Acros123 napisał(a)

Mam problem z jednym zadaniem z main'a http://main.edu.pl/pl/user.ph[...]ask&task=dzie&con=PAS
chce to zrobić w c++ . Za bruta dali mi 87 pkt jednakże chce mieć 100 , w necie szukałem gotowców i podpowiedzi jednakże nigdzie po wysłaniu nie było 100 ani nawet 87 :D .
Proszę o pomoc , najlepiej o gotowca do przeanalizowania i jeszcze czy mógłby mi ktoś wytłumaczyć czemu niektórzy stosują w warunku akurat pierwiastek z liczby n i dlaczego to jest szybsze ???

ponieważ dzielniki większe od pierwiastka n są wielokrotnościami dzielników wcześniej obliczonych (mniejszych od pierwiastka z n) :]

0

Przy najzwyklejszym sprawdzaniu dzielników starcza dojechać do sqrt(N) włącznie, ponieważ jeśli liczba ma jakiś dzielnik nietrywialny, to znajduje się on w przedziale (1,sqrt(N)>

Rozbij sobie jakąkolwiek liczbę na czynniki, przykładowo 24:
124
2
12
38
4
6
// sqrt(24) sqrt(24)
6
4
83
12
2
24*1

Zauważ, że pierwsza kolumna rośnie, a druga maleje. Gdy 46 przechodzi w 64, to dalej masz w odwrotnej kolejności czynniki, które już miałeś wcześniej. Przekręcenie to następuje za pierwiastkiem z sprawdzanej liczby.

0
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    unsigned long long n;
    cin >> n;
    double gg=sqrt(n);
    for(int i=1; i<=gg; i++) 
    {
        if(n % i == 0)
            cout << i << '\n';
    }
    for(int i=int(gg); i>=1; i--) 
    {
        if(n % i == 0)
            cout << n / i << '\n';
    }
    cout.flush();
  system("pause");
    return 0;
}

za to jest tylko 75 pkt , może to zewzględu na te kwadraty np 16 ??

0

Głupie pytanie - jak na main'ie wysłać do sprawdzenia zadanie w C++, tylko Pascala widzę.

0

Skopiowałem ci moje stare rozwiązanie na 100 pkt:

 #include <iostream>
#include <cmath>

using namespace std;

int main()
{
    unsigned long long n;
    cin >> n;
    int i;
    for(i = 1; i*i <= n; i++)
    {
        if(n % i == 0)
            cout << i << endl;
    }
    for(i--; i >= 1; i--)
    {
        if (i*i < n && n % i == 0)
            cout << n / i << endl;
    }
    cout.flush();
    return 0;
}
0

liczby mniejsze niż 10^9 nie mają więcej niż 1344 dzielniki
(w 64 bitach da się zmieścić liczbę o 184320 dzielnikach)
przy okazji znalezienia dzielnika (mniejszego od pierwiastka) można zapamiętać drugi dzielnik.

void div(int n){
    int i, t[1344/2+2],k=0;
    printf("\n%d\n", n);
    for(i=1; i*i <= n; i++)
        if( n%i==0 ){
            t[k++] = n/i;
            cout << i << "\n";
        }
    k--;
    if( t[k]*t[k]==n ) k--;  // poprawka gdy n jest kwadratem
    while( k>=0 )
        cout << t[k--] << "\n";
} 
0

Jak już przesyłamy rozwiązania, to i moje:

#include <cstdio>
#include <vector>

typedef std::vector<int> liczby;

int main()
{
int liczba;
scanf("%d", &liczba);
liczby dzielniki;

for (int i = 1; i*i <= liczba; i++)
  if (liczba%i == 0)
  {
    printf("%d\n", i);
    if (liczba/i != i)
      dzielniki.push_back(liczba/i);
  }

for (liczby::reverse_iterator it = dzielniki.rbegin();
    it != dzielniki.rend(); it++)
  printf("%d\n", *it);

return 0;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0