Codeforces 1473B - String LCM Solution

 Explain: 

codeforces tutorial : 

We should notice that if some string x$x$ is a multiple of string y$y$, then |x|$|x|$ is a multiple of |y|$|y|$. This fact leads us to the conclusion that |LCM(s,t)|$|LCM(s,t)|$ should be a common multiple of |s|$|s|$ and |t|$|t|$. Since we want to minimize the length of the string LCM(s,t)$LCM(s,t)$, then its length is LCM(|s|,|t|)$LCM(|s|,|t|)$.

So we have to check that LCM(|s|,|t|)|s|$\frac{LCM(|s|,|t|)}{|s|}$ copies of the string s$s$ equal to LCM(|s|,|t|)|t|$\frac{LCM(|s|,|t|)}{|t|}$ copies of the string t$t$. If such strings are equal, print them, otherwise, there is no solution.

Solution in C++:

 ///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5. int t,i,j,lcm,sll,tll;
6. cin>>t;
7. while(t--)
8. {
9. string s,t,s1,t1;
10. cin>>s>>t;
11. sll=s.size();
12. tll=t.size();
13. int lcm=(sll*tll)/__gcd(sll,tll);
14. for(i=0; i<lcm/sll; i++)
15. s1+=s;
16. for(j=0; j<lcm/tll; j++)
17. t1+=t;
18. if(s1==t1)
19. cout<<s1<<endl;
20. else
21. cout<<"-1"<<endl;
22. }
23. }