整数分段c++
题目描述
小 Z 有一个大整数 s,整数 s 的位数最大可能有 100 位。现在小 Z 将要将这个整数 s 分成若干段,至少两段。
问是否存在一种分段方法,可以使得分段后的每一段整数的各个数位之和相同。
「注意」
本题中的大整数 s 比较特殊,可能含有前导 0,例如输入有可能为 0134 这种整数。
输入
第一行输入测试数据组数t,t>=1 且 t<=10;
每组数据输入有2行:
每组数据第一行输入一个整数 n,表示大整数 s 的位数。2≤n≤100。
每组数据第二行输入一个位数为 n 的大整数,即输入 n 个数字字符,每个数字字符都为 0 - 9 之间的字符,可能含有前导 0。
输出
输出t行
每行输出 YES 或者 NO。
样例输入
3
5
73452
6
000000
3
232
样例输出
YES
YES
NO
示例代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(ll x,string b){
ll s=0;
for(int i=0;i<b.size();i++){
s=s+b[i]-'0';
if(s==x) s=0;
}
if(s==0) return 1;
else return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll t;
cin>>t;
while(t--){
ll n,sum=0;
cin>>n;
string a;
cin>>a;
for(int i=0;i<a.size();i++){
sum+=(a[i]-'0');
}
if(sum==0){
cout<<"YES\n";continue;
}
bool v=0;
for(int i=1;i<sum;i++){
if(sum%i==0){
if(check(i,a)==1){
v=1;break;
}
}
}
if(v==0) cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}