Bella: /* Alte probleme similare */

2018-10-13T23:09:19Z

Alte probleme similare

New page

== TEMA Rezolvari==
=== Descompunere in factori primi si nr divizoril ===
* [http://varena.ro/problema/nenepatrat nepatrat][http://isa.algopedia.ro/wiki/index.php/nenepatrat Rez]
* [https://www.infoarena.ro/problema/divmul divmul][http://isa.algopedia.ro/wiki/index.php/divmul Rez]

=== Ciur ===
* [http://varena.ro/problema/paisprezece paisprezece] [http://isa.algopedia.ro/wiki/index.php/paisprezece Rez]
* [https://infoarena.ro/problema/prim prim][http://isa.algopedia.ro/wiki/index.php/prim Rez]
== Nenepatrat ==
<syntaxhighlight>
/*
fie n = d1^p1* ... * dn^pn
Nr de divizori ai lui n: nrdiv = (p1+1)*..*(pn+n)
Nr de divizori ai lui n^2: nrdivp = (2p1+1)*..*(2pn+n)
Nr de divizori ai lui n^2 mai mici decat n, inclusiv n: (nrdivp+1)/2
(numarul lde divizori ai unui patrat perfect este impar)
Din acestia vom scadea nr de divizori ai lui n.
*/
#include <stdio.h>

int main() {
int d, p, n, nrdiv, nrdivp;

FILE *fin = fopen( "nenepatrat.in", "r" );
FILE *fout = fopen( "nenepatrat.out", "w" );
fscanf( fin, "%d", &n );

// calculam numar divizori ai lui n si ai lui n^2
d = 2; nrdiv = nrdivp = 1;
while ( d * d <= n ) {
p = 0;
while ( n % d == 0 ) {
n /= d;
p++;
}
nrdiv *= p + 1;
nrdivp *= 2 * p + 1;
d++;
}
if ( n > 1 ) {
nrdiv *= 2;
nrdivp *= 3;
}

fprintf( fout, "%d\n", (nrdivp + 1)/ 2 - nrdiv );
fclose( fin );
fclose( fout );

return 0;
}
</syntaxhighlight>

== Divmul ==
<syntaxhighlight>
/*
nr1 = a * x
nr2 = b * x;
y = a * b * x; //cmmmc
unde a si b sunt prime intre ele
a * b = y / x;
Cate perechi a, b pot avea .
Daca descompunem in factori primi pe y/x = d1^p1 * d2^p2 *... *dn^pn,
fiecare factor va putea aparea doar intr-unul din numerele a, b. Astfel ca
va avea 2^n posibilitati de a forma pe a.
*/

#include <stdio.h>

int main()

{
FILE *fin, *fout;
int t, x, y, num, d;
fin = fopen("divmul.in", "r");
fscanf(fin, "%d", &t);
fout = fopen("divmul.out", "w");
for (t; t > 0; --t) {
fscanf(fin, "%d%d", &x, &y);
if (y % x != 0)
fprintf(fout, "0\n");
else {
y /= x;
num = 1;
d = 2;
while (d * d <= y) {
if (y % d == 0) {
while (y % d == 0)
y /= d;
num *= 2;
}
++d;
}
if (y > 1)
num *= 2;
fprintf(fout, "%d\n", num);
}
}
fclose(fin);
fclose(fout);
return 0;

}
</syntaxhighlight>

== Prim ==

<syntaxhighlight>
#include <stdio.h>
#define MAX 1300000

char ciur[1 + MAX];
int prim[100030], con = 0;
int main(){
FILE*fi,*fo;
fi=fopen("prim.in","r");
fo=fopen("prim.out","w");

for(int i = 2; i * i <= MAX; i++)
if(ciur[i] == 0)
for(int j = i * i; j <= MAX; j += i)
ciur[j] = 1;
for(int i = 2; i <= MAX; i++)
if(ciur[i] == 0)
prim[con++] = i;

int k;
fscanf(fi,"%d", &k);
fprintf(fo,"%lld", 1LL * prim[k] * prim[k]);

fclose(fi);
fclose(fo);
return 0;
}
</syntaxhighlight>

== Paisprezece ==

<syntaxhighlight>
#include <stdio.h>
#define CMAX 100000
char ciur[CMAX+1];
int v[300000], k, d; // vector cu nr prime
int main(){
FILE *fin = fopen( "paisprezece.in", "r" );
FILE *fout = fopen( "paisprezece.out", "w" );
int x, y, i, j, p6, p13, cnt;

fscanf(fin, "%d%d", &x, &y );

v[0] = 2; k = 1;
for(d = 3; d <= CMAX; d +=2 )
if( ciur[d] == 0 ){ // daca d e prim
v[k++] = d; // pun val d in vectorul v
for(long long i = 1LL * d * d; i<= CMAX; i = i + 2 * d ) // marchez ca neprime
ciur[i] = 1;
}
cnt = 0;
printf("%d\n",v[0] );

// daca n ar fi de forma d^13, nu am putea avea ca d decat pe 2 sau pe 3
for(i = 0; i < 2; i++ ){
p13 = 1;
for(j = 0; j < 13; j++ )
p13 *= v[i];
if(p13 >= x && p13 <= y )
cnt++;
}

i = 0;
p6 = v[0]*v[0]*v[0]*v[0]*v[0]*v[0];
while ( p6 < y ){
j = 0;
while ( v[j] * p6 <= y ){
if ( i != j && v[j]*p6 >= x ){
cnt ++;
printf("%d %d %d\n",v[i], v[j], p6*v[j] );
}
j++;
}
i++;
p6 = v[i]*v[i]*v[i]*v[i]*v[i]*v[i];
}

fprintf(fout,"%d\n", cnt );
fclose(fin);
fclose(fout);
return 0;
}
</syntaxhighlight>

<syntaxhighlight>
// Sol Cella Florescu
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000000

char ciur[MAXN + 1] = {0, 1};

inline long long la_putere(long long baza, int exponent) {
long long rez = 1LL;
int i;
for (i = 0; i < exponent; ++i)
rez *= baza;
return rez;
}

inline int numere_speciale_pana_in_N(int n) {
int rez, num1, num2, num_prime;
num1 = 2;
rez = 0;
while (la_putere(num1, 13) <= n) {
++rez;
++num1;
}
num1 = 2;
num_prime = 0;
for (num2 = 2; num2 <= MAXN; ++num2)
num_prime += 1 - ciur[num2];
num2 = MAXN;
while (num1 <= 19 && num_prime > 0) {
while (la_putere(num1, 6) * num2 > n) {
num_prime -= 1 - ciur[num2];
--num2;
}
if (num2 > 1 && ciur[num1] == 0) {
if (num1 <= num2)
rez += num_prime - 1;
else
rez += num_prime;
}
++num1;
}
return rez;
}

int main()
{
FILE *fin, *fout;
int x, y, i, j;
for (i = 2; i * i <= MAXN; ++i)
if (ciur[i] == 0)
for (j = i * i; j <= MAXN; j += i)
ciur[j] = 1;
fin = fopen("paisprezece.in", "r");
fscanf(fin, "%d%d", &x, &y);
fclose(fin);
fout = fopen("paisprezece.out", "w");
fprintf(fout, "%d\n", numere_speciale_pana_in_N(y) - numere_speciale_pana_in_N(x - 1));
fclose(fout);
return 0;
}
</syntaxhighlight>

<syntaxhighlight>
//Solutie Matei T.
#include <stdio.h>
#define MAX_PRIM 1000000//aproximativ cel mai mare numar prim pe care il putem avea
#define MAX_PRIM_6 19//cel mai mare nr prim care ridicat la puterea 6 nu depaseste y
#define MAX_PRIM_13 3//-------------------//----------------------- 13 nu depaseste y
#define NR_PRIME 10000 //nr de numere prime

char ciur[ 1 + MAX_PRIM ];
int prime[ NR_PRIME ];

//calculam o putere in timp logaritmic
int putere( int baza , int exp , int acum ) {
if( exp == 0 )
return acum;
else if( exp % 2 == 1 )
return putere( baza * baza , exp / 2 , acum * baza );
else
return putere( baza * baza , exp / 2 , acum );
}

int main() {
int i , d , j , x , y , solutii , nr , nPr;
j = 0;
//folosim un ciur pentru 8 numere prime
for( d = 2 ; d <= MAX_PRIM ; d++ )
if( ciur[ d ] == 0 ) {
prime[ j ] = d;
j++;
for( i = 2 * d ; i <= MAX_PRIM ; i = i + d )
ciur[ i ] = 1;
}

nPr = j;

FILE *fin = fopen( "paisprezece.in" , "r" );
fscanf( fin , "%d%d" , &x , &y );
fclose( fin );

//luam fiecare solutie de forma p^13 cu p prim
i = 0;
solutii = 0;
while( prime[ i ] <= MAX_PRIM_13 ) {
nr = putere( prime[ i ] , 13 , 1 );
if( x <= nr && nr <= y )
solutii++;
i++;
}

//luam fiecare solutie cu p * q ^ 6 cu p si q prim
i = 0;
while( prime[ i ] <= MAX_PRIM_6 ) {
nr = putere( prime[ i ] , 6 , 1 );
j = 0;
while( prime[ j ] * nr <= y && j < nPr ) {
if( prime[ i ] != prime[ j ] && x <= prime[ j ] * nr )
solutii++;
j++;
}
i++;
}

FILE *fout = fopen( "paisprezece.out" , "w" );
fprintf( fout , "%d" , solutii );
fclose( fout );
return 0;
}
/*

Stiim ca un numar de forma:
p1^e1 * p2^e2 * ... * pn^en unde p1 , p2 , ... , pn sunt nre prime
are nr de divizori egal cu ( e1+1 ) * ( e2+1 ) * ... * ( en+1 )

14 = 1 * 14 = 2 * 7

=> un numar este ori p^13 ori p * q^6

*/
</syntaxhighlight>

= Lectie =
== Construirea unui vector de numere prime ( Comparcatarea ciurului ) ==
<syntaxhighlight>
/*
Dorim sa contruim un vector de numere prime mai mici sau egale cu o val data VMAX
Ne vom folosi deci de ciurul lui Eratostene pentru a determina care numere sunt prime pana la VMAX
Vom ignora numerele pare atunci cand marchez numerele neprime, neaccesand nicioadata aceste pozitii
Vom marca penru un divizor d divizorii acestuia impari: d * d, d*(d+2), ....Sar peste elementele d*(d+1), d*(d+3) acestea fiind numere pare
*/

#define VMAX 1000000
char ciur[VMAX+1] = {0};
int prime[300000]; // dimensiunea vectorului este data de numarul de numere prime pe care le-as putea gasi pena la VMAX

int main(){
.................
// marcam in ciur numerele impare prime
for(int d = 3; d * d <= VMAX; d +=2 )
if( ciur[d] == 0 )
for(int i = d * d; i<= VMAX; i = i + 2 * d )
ciur[i] = 1;
// punem nr 2 in vectorul de numere prime, fiind singurul nr par prim
prime[0] = 2;
// parcurgem ciurul doar pe pozitiile impare si construim vectorul de numere prime
k = 1;
for( d = 3; d <= VMAX; d += 2 )
if( ciur[d] == 0 )
prime[k++] = d;
...................
}
</syntaxhighlight>

<syntaxhighlight>
#define VMAX 1000000

char ciur[VMAX] = {0};
int prime[300000];

v[0] = 2; k = 1;
for(d = 3; d <= 1000000; d +=2 )
if( ciur[d] == 0 ){ // daca d e prim
prime[k++] = d; // pun val d in vectorul v
for(long long i = 1LL * d * d; i<= 1000000; i=i+2*d ) // marchez ca neprime
ciur[i] = 1;
}
</syntaxhighlight>

https://infoarena.ro/problema/divprim

= Tema =
* [http://varena.ro/problema/prime prime] [http://isa.algopedia.ro/wiki/index.php/prime Rez]
* [http://varena.ro/problema/prime1 prime1] [http://isa.algopedia.ro/wiki/index.php/prime1 Rez]
* [http://varena.ro/problema/sprime sprime], XOR 2015 [http://isa.algopedia.ro/wiki/index.php/sprime Rez]
* [https://infoarena.ro/problema/divprim divprim] [http://isa.algopedia.ro/wiki/index.php/divprim Rez]
== Optional ==
* [http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=365 prime] Campion2005 [http://isa.algopedia.ro/wiki/index.php/prime_campion Rez]
* [http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1176] [http://isa.algopedia.ro/wiki/index.php/bileprime_campion Rez]
== Alte probleme ==
* [http://varena.ro/problema/extraprime extraprime]
*[http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=710 Prime1_campion] Sansa de a fi campion 2002

Cerc 6 2018 lectia 3 - Revision history

Bella: /* Alte probleme similare */