infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Octombrie 23, 2005, 21:49:46


Titlul: 124 Divizor si multiplu
Scris de: ditzone din Octombrie 23, 2005, 21:49:46
Aici puteţi discuta despre problema Divizor si multiplu (http://infoarena.ro/problema/divmul).

Titlul: 124 Divizor si multiplu
Scris de: Ovidiu Rosca din Noiembrie 07, 2005, 21:20:10
In ce complexitate se face problema asta? Ca am incercat diverse variante care nu se incadrau in timp...

Titlul: 124 Divizor si multiplu
Scris de: Bogdan-Cristian Tataroiu din Noiembrie 08, 2005, 18:02:07
Eu am O(sqrt(N))

Titlul: 124 Divizor si multiplu
Scris de: Adriana Sperlea din Noiembrie 13, 2005, 12:33:48
Citat din mesajul lui: bogdan2412
Eu am O(sqrt(N))


 :-k cine e N? in problema citesti un x, un y, tre sa afisezi un p, un q dar....nimic de N

Titlul: 124 Divizor si multiplu
Scris de: VladS din Noiembrie 13, 2005, 13:26:17
N e Y/X.  E ceva cu divizorii lui Y/X  :roll:

Titlul: 124 Divizor si multiplu
Scris de: Adriana Sperlea din Noiembrie 13, 2005, 13:31:31
vai, iti multumesc :) m-am prins si io din moment ce cmmmc(a,b) = a *b/cmmdc(a,b). numai ca nu ti se pare ciudat sa zici O(sqrt(N)) cand in problema nu exista N? :?: la asta ma refeream.

Titlul: 124 Divizor si multiplu
Scris de: u-92 din Noiembrie 13, 2005, 14:37:44
nu chiar.. log(n) complexitate logaritmica, n^2 complexitate patratica, sqrt(n)
complexitate (cum se zice aici? :mrgreen:).. oricum, cam asta e ideea

Titlul: 124 Divizor si multiplu
Scris de: Adriana Sperlea din Noiembrie 13, 2005, 15:16:32
atunci, my bad :oops: am zis si eu asa, plina de inocentza si doar cu ganduri de pace :peace:

Titlul: 124 Divizor si multiplu
Scris de: Vlad Berteanu din Noiembrie 13, 2005, 21:56:28
In momentul in care iti zice O(sqrt(y/x)) ti se sugereaza si o rezolvare...si daia cred ca bogdan ti a zis sqrt(n)  :P

Titlul: 124 Divizor si multiplu
Scris de: Adriana Sperlea din Noiembrie 14, 2005, 12:06:28
ma rog, nu mi-a zis mie :)

Titlul: 124 Divizor si multiplu
Scris de: Rus Cristian din Noiembrie 17, 2005, 16:57:57
ce da pt
Cod:
2
2 4219164
3 4

si inca ceva...solutia...se incadreaza in 2^31?.... :-'

never mind...e bine...gresala era alta...si...dupa niste calcule am aflat ca rezultatul se incadreaza in 2^31... :roll:

Titlul: Raspuns: 124 Divizor si multiplu
Scris de: Toma Radu din Iulie 09, 2006, 18:54:24
Imi zice si mie cineva cat da pe:

Cod:
5
5 30
2 120
3 630
5 4410
1 9699690

? va rog...

Titlul: Raspuns: 124 Divizor si multiplu
Scris de: u-92 din Iulie 10, 2006, 10:26:01
Cod:
4
8
16
8
256

Titlul: Raspuns: 124 Divizor si multiplu
Scris de: Toma Radu din Iulie 11, 2006, 13:53:08
daca nu exista solutie ce se va afisa?

Titlul: Raspuns: 124 Divizor si multiplu
Scris de: Filip Cristian Buruiana din Iulie 11, 2006, 13:57:54
Ce inseamna nu exista solutie? Daca nu va exista nici o pereche (p q) se va afisa 0.

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Dragos Oprica din Februarie 20, 2009, 17:02:50
ma ajuta cineva si pe mine: am incercat sa fac ca in articolul cu solutii, dar nu stiu o metoda eficienta de a afla toti divizorii lui y/x in timp rapid.

Multumesc anticipat

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Andrei Grigorean din Februarie 20, 2009, 17:16:25
O(sqrt(N)) e destul de bine?

Daca N se divide cu x atunci putem scrie N = x * y. Observam ca nu putem avea simultan x > sqrt(N) si y > sqrt(N). De aici rezulta codul:

Cod:
int i;
for (i = 1; i * i < N; ++i)
    if (N % i == 0)
        printf("%d\n%d\n", i, N/i);
if (i * i == N)
    printf("%d\n", i);

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Dragos Oprica din Februarie 20, 2009, 17:20:52
multumesc frumos wefgef
acuma ar trebui sa o fac =D&gt;

Titlul: Exemplu:
Scris de: [email protected] din Noiembrie 03, 2009, 21:01:42
Adica daca d(divizorul)D10=1,2,5,10 


Nu???? :-k :-s

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Simoiu Robert din Martie 17, 2010, 16:49:03
Nu inteleg ce ai scris tu acolo  :eyebrow:

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: c a e n din Mai 14, 2011, 17:44:00
Nu prea inteleg cum sa fac factorizarea rapida. Imi poate explica/da un link cineva? Multumesc!

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: UAIC.VlasCatalin din Iulie 13, 2011, 23:39:19
Nu stiu unde pot vedea articolul cu solutii, dar poate cineva sa-mi dea si mie un hint, care e faza cu divizorii lui y/x?
Poate macar un link ceva....

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Simoiu Robert din Iulie 14, 2011, 08:06:38
http://infoarena.ro/happy-coding-2005-2/solutii

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: UAIC.VlasCatalin din August 15, 2011, 01:46:12
Chiar nu inteleg de ce iau incorect la problema asta, fac exact ca in articol, aflu toti divizorii lui y/x daca y se imarte exact la x, numaru determinat fiind nr=D "din articol", daca y nu se imparte exact la x atunci tiparesc 0, nu stiu ce pot sa mai fac, pe testele mele merge bine, pe testul exemplu si pe cel din comentarii la fel merge bine dar oricum WA  ](*,)

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: George Marcus din August 15, 2011, 12:28:36
Puterea lui 2 ai pus-o longint?
In rest, habar n-am. Poate ne ajuta o sursa.

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: UAIC.VlasCatalin din August 15, 2011, 13:35:30
E OK, s-a facut, a fost totusi o greseala din partea mea, uitasem sa precaut cazul cind exista un divizor prim mai mare decit numerele prime pe care le-am generat eu :aha: :ok:

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: George Marcus din August 15, 2011, 14:22:21
Nu era necesar sa generezi numere prime pentru factorizare.

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: FMI Ciprian Olariu din Iulie 16, 2012, 13:01:23
Cred ca e posibil sa existe un test in care nu se respecta restrictia Y<=100.000.000 :thumbdown: Am verificat cu sursa asta (http://infoarena.ro/job_detail/768230) punand
Cod:
assert(X<=10000 && Y<=100000000);
si ia KBS 6. Sursa aceea (aici (http://infoarena.ro/job_detail/735743)) fara assert ia incorect deoarece eu precalculam numerele prime mai mici ca 10000 (mai mici ca radical din Y). :-k

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Vasilut Lucian din Octombrie 30, 2012, 20:44:32
 :) Buna seara.Cred ca exista unele teste care nu respecta cerinta din enunt ca Y<=100.000.000 deoarece am pus assert(x<=10000 && y<=1000000000) si iau Killed By Signal 6 ](*,)

L.E .Am gasit o greseala in programul meu si de aia luam 0 pct.Oricum ramane valabila observatia ca exista unele teste care au y > 100000000.

O seara placuta!!!!

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Tudorica Andrei din Ianuarie 17, 2013, 17:58:56
pfff la problema asta chiar nu imi dau seama ce ar putea fi gresit #-o fac ca si in descriere si nici macar un test nu puncteaza, desi testele care mi le-am dat eu merg. Vreo sugestie/idee? :D

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Petru Trimbitas din Ianuarie 17, 2013, 19:49:58
Incearca sa rezolvi problemele si singur. Nu prea te ajuta daca primesti de fiecare data teste :)

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Tudorica Andrei din Ianuarie 18, 2013, 16:43:13
nu am cerut teste... am cerut o idee...

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Strimbu Alexandru din Noiembrie 29, 2013, 21:36:06
De ce nu merge codul acesta?
Cod:
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

long long cmmdc(long long a,long long b)
{
    long long c;
    while(b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}

int main()
{
    ifstream fin("divmul.in");
    ofstream fout("divmul.out");
    long long t,i,x,y,k,a,b,c,nr;
    long long prod;
    fin>>t;
    for(k=1;k<=t;k++)
    {
        nr=0;
        fin>>x>>y;
        prod=x*y;
        for(i=1;i*i*x*x<=prod;i++)
        {
            a=i*x;
            if(prod%a==0)
            {
                b=prod/a;
                c=cmmdc(a,b);
                if(c==x&&a*b/c==y)
                {
                    nr+=2;
                    if(a*a==prod)
                        nr--;
                }
            }
        }
        cout<<nr<<"\n";
    }
    return 0;
}

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Zamfir Ovidiu din Iunie 17, 2014, 23:22:05
Am facut problema cum scrie in articol,insa iau TLE.
Ma poate ajuta cineva ?

#include <fstream>
#include <cmath>

using namespace std;
long int t,n,x,k,y,nr,i,v[50500],a[50500],x1,yy;
int main()
{
    ifstream f("divmul.in");
    ofstream g("divmul.out");
    f>>t;
    for(k=1;k<=t;k++)
    {
        f>>x>>y;x1=x;yy=y;nr=0;
        for(i=2;i<=sqrt(x) && x1>1;i++)
            while(x1%i==0) v++,x1/=i;
        if(x1==x) v[x1]=1;
        for(i=2;i<=sqrt(y) && yy>1;i++)
        {
            if(v) a=v,yy/=pow(i,v);
            while(yy%i==0) a++,yy/=i;
            if(a>v) nr++;
            a=0;v=0;
        }
        g<<(1 << nr)<<'\n';
    }
    f.close();g.close();
    return 0;
}


Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Duta Vlad din Iunie 18, 2014, 00:18:18
In primul rand scoate sqrt() din for. Conditia aia se evalueaza la fiecare pas, iar radicalul e o operatie foarte lenta. In plus cred ca ai putea sa te opresti cand i*i > x1, pentru ca altfel x1 % i nu va fi niciodata 0. La fel si pt y.
Cu v si a nu prea ma prind care e treaba ca sunt declarati vectori dar sunt folositi ca variabile...

Titlul: Răspuns: 124 Divizor si multiplu
Scris de: Mihai Calancea din Iunie 18, 2014, 00:33:54
Nu le foloseste ca variabile, dar daca nu lasi spatii "[i ]" inseamna italics  :)


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines