Cerc 6 2018 lectia 3
From Algopedia
TEMA Rezolvari
Descompunere in factori primi si nr divizoril
Ciur
Nenepatrat
/*
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;
}Divmul
/*
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;
}Prim
#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;
}Paisprezece
#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;
}// 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;
}//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
*/Lectie
Construirea unui vector de numere prime ( Comparcatarea ciurului )
/*
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;
...................
}
#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;
}
https://infoarena.ro/problema/divprim
Tema
Optional
Alte probleme
- extraprime
- Prime1_campion Sansa de a fi campion 2002
