Pagini recente » Cod sursa (job #1414836) | Cod sursa (job #1362814) | Cod sursa (job #431261) | Cod sursa (job #953262) | Cod sursa (job #1700213)
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int NMAX = 1000005;
bool c[NMAX];
int v[NMAX],
prs[NMAX];
int n, m;
void erat(int lim) {
int top=0;
c[0] = 1;
c[1] = 1;
for(int i=4; i<=lim; i+=2)
c[i] = 1;
for(int i=3; i*i<=lim; i+=2) {
if(c[i])
continue;
for(i64 j=i*i; j<=lim; j+=i+i)
c[j] = 1;
}
prs[top++]=2;
for(int i=3; i<=lim; i+=2)
if(!c[i])
prs[top++]=i;
}
inline int cbits(int arg) {
int ans = 0;
while(arg) {
if(arg&1)
++ans;
arg>>=1;
}
return ans;
}
inline int pinex(int arg) {
int fct[15];
int tmp,
ans = 0,
top = 0;
for(int i=0; 1LL*prs[i]*prs[i]<=arg; ++i) {
if(arg%prs[i])
continue;
while(!(arg%prs[i]))
arg/=prs[i];
fct[top++] = prs[i];
}
if(arg>1)
fct[top++] = arg;
for(int i=1; i<(1<<top); ++i) {
tmp = 1;
for(int j=0; (1<<j)<=i; ++j)
if(i&(1<<j))
tmp *= fct[j];
if(cbits(i)&1)
ans+=(n-1)/tmp;
else
ans-=(n-1)/tmp;
}
return ans;
}
int main(void) {
FILE *fi = fopen("mins.in","r");
FILE *fo = fopen("mins.out","w");
i64 ans;
fscanf(fi,"%d%d",&n,&m);
ans = (1LL*n-1)*(m-1);
erat(max(n, m));
if(m>n)
swap(n, m);
for(int i=2; i<m; ++i)
ans-=pinex(i);
fprintf(fo,"%lld\n",ans);
fclose(fi);
fclose(fo);
return 0;
}