Pagini recente » Cod sursa (job #3347162) | Cod sursa (job #3351879) | Cod sursa (job #3303371) | Cod sursa (job #954340) | Cod sursa (job #3304993)
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream cin("mins.in");
ofstream cout("mins.out");
const int VMAX=1e6;
int lin, col;
bool ciur[VMAX+5];
vector<int> primes;
void generate_primes(){
for(int i=2;i<=VMAX;i++){
ciur[i]=true;
}
for(int i=2;i<=VMAX;i++){
if(ciur[i]){
for(int j=2*i;j<=VMAX;j+=i){
ciur[j]=false;
}
primes.push_back(i);
}
}
}
vector<long long> get_primes(long long n){
vector<long long> ans;
int d=0;
while(d<primes.size()&&primes[d]*primes[d]<=n){
if(n%primes[d]==0){
ans.push_back(primes[d]);
while(n%primes[d]==0){
n=n/primes[d];
}
}
d++;
}
if(n>1){
ans.push_back(n);
}
return ans;
}
long long query(long long A, long long B){
vector<long long> primes=get_primes(B);
int x=primes.size();
long long ans=0;
for(int i=0;i<(1<<x);i++){
long long p=1;
int cnt=0;
for(int j=0;j<x;j++){
if(i&(1<<j)){
p=p*primes[j];
cnt++;
}
}
if(cnt%2==0){
ans+=A/p;
}
else{
ans-=A/p;
}
}
return ans;
}
int main(){
cin>>lin>>col;
long long ans=0;
for(int i=1;i<lin;i++){
ans+=query(col-1, i);
}
cout<<ans;
}