Mins

În planul xOy se desenează un dreptunghi cu laturile paralele cu axele de coordonate. Coordonatele vârfurilor stânga-jos şi dreapta-sus ale dreptunghiului sunt: (0,0) şi (c,d). Fie P mulţimea punctelor situate în interiorul dreptunghiului, ale căror coordonate sunt numere naturale. Prin desenarea unui număr minim m de segmente de dreaptă, se uneşte vârful de coordonate (0,0) cu fiecare punct din mulţimea P. Astfel, fiecare punct din P va aparţine interiorului unui segment din cele m sau va fi o extremitate a unui segment din cele m.

Cerinţă

Scrieţi un program care să citească numerele naturale c şi d, şi care să determine numărul minim m de segmente de dreaptă desenate. 

Date de intrare

Fişierul de intrare mins.in conţine o singură linie pe care sunt scrise două numere naturale c şi d, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire mins.out va conţine o singură linie pe care se va scrie un număr natural reprezentând numărul minim m de segmente de dreaptă desenate.

Restricţii şi precizări

• c, d sunt numere naturale nenule.
• 1 ≤ c, d ≤ 1 000 000
• Pentru 50% dintre teste, c, d ≤ 5000.
• Pentru 80% dintre teste, c, d ≤ 200 000.

Exemplu

mins.in	mins.out
4 3	5

Explicaţie

Pentru c=4, d=3, mulţimea P a punctelor de coordonate naturale, situate în interiorul dreptunghiului, este formată din 6 puncte: {P1,P2,P3,P4,P5,P6}. Pentru a uni vârful stanga-jos al dreptunghiului, (0, 0) cu cele 6 puncte sunt suficiente 5 segmente.

#include <iostream>
	
#include <fstream>
	
using namespace std;
	
 
	
ifstream f("mins.in");
	
ofstream g("mins.out");
	
 
	
const int MAX = 1000001;
	
 
	
int ciurn[MAX],///Vector al numarului de divizori primi
	
    ciurp[MAX],///Ciurul numerelor divizibile cu patrate de numere prime(i.e. la care nu toti divizorii primi nu sunt distincti)
	
    c, d, n;
	
 
	
long long card;
	
 
	
void calcul(int i)
	
{
	
    if(ciurn[i] == 0)
	
    {
	
        for(int j = i; j <= n; j += i)
	
            ciurn[j]++;
	
        long long k = 1LL * i * i;
	
        for(long long jj = k; jj <= n; jj += k)
	
            ciurp[jj] = 1;
	
    }
	
    if(ciurp[i]==0)
	
    {
	
        long long t=1LL*(c/i)*(d/i);
	
        if(ciurn[i]%2==0)
	
            card-=t;
	
        else
	
            card+=t;
	
    }
	
}
	
 
	
int main()
	
{
	
    f>>c>>d;
	
    c--;
	
    d--;
	
    n=min(c,d);
	
    for(int i=2;i<=n;i++)
	
        calcul(i);
	
    g<<1LL*c*d-card;
	
    f.close();
	
    g.close();
	
    return 0;
	
}

#include <fstream>
#include <bitset>
 
using namespace std;
 
#define ll long long int
 
ifstream cin("mins.in");
ofstream cout("mins.out");
 
const int DIM = 1000000+1;
 
int  ciur[DIM];
bitset<1> valid[DIM]={0};
int C, D;
 
int main()
{
 
    cin>>C>>D;
    C--; D--;
 
    int minCD = min(C, D);
    ll sol = 1LL * C * D;                   /// total puncte
 
    for(int i = 2;i <= minCD;i++ )
    {
        if(ciur[i] > 0)
            continue;                       /// neprim continua
 
        for (int j = i;j <= minCD; j += i ) /// ciur
            ciur[j]++;
 
        if(1LL * i * i <= minCD )           /// sqrt prime factor ciur
            for (int j = i*i;j <= minCD;j += i*i)
                valid[j] = 1;
    }
 
    for ( int i = 2; i <= minCD;i++){
        if(valid[i] == 0){
            if(ciur[i]%2 == 1)
                sol -= 1LL*(C/i)*(D/i);
            else
                sol += 1LL*(C/i)*(D/i);
        }
    }
    cout<<sol;
 
    return 0;
}