Cod sursa(job #3304993)

Utilizator lucaje123Vartolomei Luca lucaje123 Data 29 iulie 2025 12:08:24
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#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;
}