--------------------------------------------------------editorial----------------------------------------------------
this is a interesting problem, main thing is how to check remainder of the suffix , which is done in this problem in a very good way just see that
// prefix remainder of the first number
At first, let’s check all prefixes of specified number — do they have remainder 0 when divided by the a? It can be done with asymptotic behavior O(N), where N -length of specified number C. If we have remainder of division by a of prefix, which ends in position pos, we can count remainder in position pos + 1: rema[pos + 1] = (rema[pos] * 10 + C[pos + 1]) % a.
//suffix remainder calculation
lets say suffix remainder is remainder when number is divided by b from (i to n-1),
for(int i=n-1;i>0;i--)
{
val=(dist[end-i]*(s[i]-'0')+val)%b;
if(val==0 && has1[i-1]==0 && s[i]!='0')
{
pos=i;
break;
}
}
Then we need to check suffixes.If we have remainder of division by b of suffix, which begin in position pos, we can count remainder of
initially remainder[n]=0,(for suffix remainder calculation)
position pos - 1: remb[pos - 1] = (C[pos - 1] * P + remb[pos]) % b, where P — it is 10^(L - 1) module b, L — length of suffix (P we can count parallel).
Now let’s check all positions pos — can we cut specified number C in this position. We can do it if next four conditions performed: prefix of number C, which ends in pos is divisible by a; suffix of number C, which begin in pos + 1 is divisible by b; length of prefix and suffix more than 0; first digit of suffix is different from 0. If all four conditions performed we found answer. If we did not find any such positions, than print NO.
---------------------------------------------code-----------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int has1[1000000],has2[1000000];
int dist[1000010];
int main()
{
lli a,b;
string s;
cin>>s;
cin>>a>>b;
lli val;
val=1;
dist[0]=1;
for(int i=1;i<=1000000;i++)
{
val=val*10;
val%=b;
dist[i]=val;
// cout<<i<<dist[i]<<endl;
}
// cout<<"here";
int n=s.length();
lli val1=0,val2=0;
for(int i=0;i<n;i++)
{
val1=val1*10+(s[i]-'0');
val1%=a;
has1[i]=val1;
}
int pos=-1;
val=0;
int end=n-1;
for(int i=n-1;i>0;i--)
{
// cout<<dist[end-i]<<endl;
val=(dist[end-i]*(s[i]-'0')+val)%b;
// cout<<" val "<<val<<endl;
if(val==0 && has1[i-1]==0 && s[i]!='0')
{
pos=i;
break;
}
}
if(pos==-1)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
for(int i=0;i<pos;i++) cout<<s[i];
cout<<endl;
for(int i=pos;i<n;i++) cout<<s[i];
}
}
.
.
