제출 #485170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
485170		kshitij_sodani	Sažetak (COCI17_sazetak)	C++14	160 / 160	4 ms	204 KiB

sazetak

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n;
llo it[11];
#include <iostream>
using namespace std;
 
// Function for extended Euclidean Algorithm
llo gcdExtended(llo a, llo b, llo* x, llo* y);
 
// Function to find modulo inverse of a
llo modInverse(llo a, llo m)
{	//cout << "Inverse doesn't exist";
    llo x, y;
    llo g = gcdExtended(a, m, &x, &y);
    if (g != 1){
    	return -1;
    }

        
    else
    {
         
        // m is added to handle negative x
        llo res = (x % m + m) % m;
        return res;
        cout << "Modular multiplicative inverse is " << res;
    }
}
 
// Function for extended Euclidean Algorithm
llo gcdExtended(llo a, llo b, llo* x, llo* y)
{
     
    // Base Case
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }
     
    // To store results of recursive call
    llo x1, y1;
    llo gcd = gcdExtended(b % a, a, &x1, &y1);
 
    // Update x and y using results of recursive
    // call
    *x = y1 - (b / a) * x1;
    *y = x1;
 
    return gcd;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	llo k;
	cin>>k;
	for(llo i=0;i<k;i++){
		cin>>it[i];
	}
	llo ans=0;
	for(llo i=n;i<=n;i++){
		llo st=0;
		llo st2=0;
		if(i==n){
			st=1;
		}
		for(llo j=0;j<k;j++){
			llo x=i%it[j];
			if(x==0){
				st=1;
			}
			else if(x==1){
				st2=1;
			}
		}
		if(st==1 and st2==1){
			ans++;
		}
	}
	n--;
	for(llo i=1;i<(1<<k);i++){
		llo x=0;
		llo zz=-1;
		vector<llo> ss;
		for(llo j=0;j<k;j++){
			if((1<<j)&i){
				zz=-zz;
				if(x==0){
					x=it[j];
				}
				else{
					

					x=(x*it[j])/__gcd(x,it[j]);
					if(x>1e9){
						break;
					}
				}
			}
			else{
				ss.pb(j);
			}
		}
		if(x>1e9){
			continue;
		}
		llo co=0;
		llo x2=ss.size();
		for(llo j=1;j<(1<<x2);j++){
			llo xx=0;
			llo st=-1;
			for(llo jj=0;jj<x2;jj++){
				if((1<<jj)&j){
					st=-st;
					if(xx==0){
						xx=it[ss[jj]];
					}
					else{
						xx=(xx*it[ss[jj]])/(__gcd(xx,it[ss[jj]]));
						if(xx>1e9){
							break;
						}
					}
				}
     		}
     		if(xx>1e9){
				continue;
			}
			//cout<<i<<":"<<j<<":"<<x<<":"<<xx<<endl;
			if(__gcd(xx,x)>1){
				continue;
			}
			/*if(xx==1){
				continue;
			}*/
			//cout<<i<<":"<<j<<":"<<x<<":"<<xx<<endl;
		
			llo y=modInverse(x%xx,xx);
			/*if(y==-1){
				continue;
			}*/
			//	cout<<y<<endl;
			llo nn=n/x;
			if(y<=nn){
				co+=st*(1+(nn-y)/xx);
			}
			//co+=st*((n/(y*x)));
		}
		ans+=zz*co;
	}
	cout<<ans<<endl;




 
	return 0;
}

• Subtask 1: 160 / 160