Main - dzielniki liczby

Mam problem z jednym zadaniem z main'a http://main.edu.pl/pl/user.phtml?op=showtask&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 ???

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

Acros123 napisał(a)

Mam problem z jednym zadaniem z main'a http://main.edu.pl/pl/user.phtml?op=showtask&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) :]

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
212
38
46
// sqrt(24)* sqrt(24)
64
83
122
241

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.

#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 ??

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

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;
}

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";
} 

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;
}