글 읽기 - 1441

songibusut 2년 전 0

1441번반례 알려주세요

#include <iostream> 
#include <vector> 
#include <algorithm>
using namespace std;
long long n,l,r,a[19]={0,},ma=1,m,k,q,an;
vector<long long> v;
string binary(long long t)
{
	string s="";
	string re="";
	while(t)
	{
		if(t%2==0) s+='0';
		else s+='1';
		t/=2;
	}
	for(int i=s.length()-1;i>=0;i--)
	{
		re+=s[i];
	}
	return re;
}
string second_binary(string bin,long long mad)
{
	string s="";
	for(int i=0;i<mad;i++) s+="0";
	s+=bin;
	return s;
}
long long gcd_u(long long a,long long b)
{
	while(1)
	{
		int r=a%b;
		if(r==0) return b;
		a=b;
		b=r;
	}
}
long long gcd_a(vector<long long> g)
{
	long long result=g[0];
	for(int i=1;i<g.size();i++) result=result*v[i]/gcd_u(result,g[i]);
	return result;
}
int main()
{
	string s;
	cin>>n>>l>>r;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		ma*=2;
	}
	for(long long i=1;i<ma;i++)
	{
		s=binary(i);
		s=second_binary(s,n-s.length());
		for(long long j=0;j<s.length();j++) if(s[j]=='1') v.push_back(a[j]);
		m=gcd_a(v);
		k=l/m+1*(l%m!=0);
		q=r/m;
		if(v.size()%2==0&&m<r) an-=q-k+1;
		else if(m<r) an+=q-k+1;
		while(v.size()) v.pop_back();
	}
	cout<<an;
} 

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1441

songibusut 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말