L1-046 整除光棍

题目 L1-046 整除光棍

image-49149a71

思路分析

使用ull最多能到20位 有五个点过不去

使用高精度模拟

代码实现

ull 15/20

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

const int N=25;

ull nums[N];

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	nums[1]=1;

	for(int i=2;i<=20;i++){

		nums[i]=nums[i-1]*10+1;

	}

//	for(int i=1;i<=20;i++)	cout<<nums[i]<<endl;

	int x;cin>>x;

	for(int i=1;i<=20;i++){

		if(nums[i]%x==0){

			cout<<nums[i]/x<<" "<<i;

			return 0;

		}

	}

	return 0;

}

ac

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

vector<int> big_div(vector<int> A,int b,int& r){

	vector<int> C;

	r=0;

	for(int i=A.size()-1;i>=0;i--){

		r=r*10+A[i];

		C.push_back(r/b);

		r%=b;

	}

	reverse(C.begin(),C.end());

	while(C.size()>1 && C.back()==0)	C.pop_back();

	return C;

}

vector<int> str2big(const string& s){

	vector<int> res;

	for(int i=s.size()-1;i>=0;i--){

		if(isdigit(s[i]))	res.push_back(s[i]-'0');

		else if(s[i]=='-' && i==0)	break;

	}

	while(res.size()>1 && res.back()==0)	res.pop_back();

	return res;

}

string big2str(const vector<int>& A){

	string res;

	for(int i=A.size()-1;i>=0;i--)

		res+=to_string(A[i]);

	return res.empty()?"0":res;

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int x;cin>>x;

	string s="1";

	vector<int> A;

	while(true){

		A=str2big(s);

		int r;

		vector<int> ans=big_div(A,x,r);

		if(r==0){

			cout<<big2str(ans)<<" "<<s.size();

			break;

		}

		s+="1";

	}

	return 0;

}

同类题型

视频讲解

⬅️ L1-045 宇宙无敌大招呼 🏠 00-天梯赛 ➡️ L1-047 装睡