Pagini recente » Cod sursa (job #2880359) | Cod sursa (job #2600917) | Cod sursa (job #1194257) | Cod sursa (job #2253805) | Cod sursa (job #2951288)
#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)
///daca avem (i, j) si d=cmmdc(i, j), d!=1 => am traversat (i/d, j/d) si cmmdc(i/d, j/d)=1
///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;
if(c>d)
swap(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]++;
}
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;
}