Pagini recente » Cod sursa (job #893758) | Cod sursa (job #2394879) | Cod sursa (job #1268613) | Cod sursa (job #2402448) | Cod sursa (job #2951290)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("mins.in");
ofstream fout("mins.out");
int c, d;
long long rez;
int a[1000100], b[1000100];
int main() {
///daca segmentul trece prin (i, j), va trece si prin (2*i, 2*j) si prin (3*i, 3*j)
///trasam segmente intre (0, 0) si (i, j)
///ce putem face sa calculam nr de segmente?
///ne intereseaza nr de perechi de nr care sunt prime intre ele
///seamana cu problema pairs adica facem ciurul, dar nu mai trebuie sa calculam nrm[i]
///avem c/i posibilitati care se divid cu i pt prima coord si d/i posibilitati care se divid cu a doua coord
///deci nu mai calculam nrm[i] si sol+=(c/i)*1LL*(d/i);
fin>>c>>d;
c--;
d--;
int minim=min(c, d);
rez=1LL*c*d;
for(int i=2; i<=minim; i++)
{
if(a[i]==0) {
for (int j = 1; 1LL * j * i <= minim; j++) {
a[1LL * i * j]++;
}
for (int j = 1; 1LL * j * i * i <= minim; j++) {
b[j * i * i] = 1;
}
}
if(b[i]==0)
{
long long val=1LL*(c/i)*(d/i);
if(a[i]%2==1)
{
rez-=val;
}
else
{
rez+=val;
}
}
}
fout<<rez;
return 0;
}