Angel's oath

topic

TENSHI was very lucky to be chosen as the angel holding the key of wisdom. She must, like other newly elected angels, take an oath before taking office. The swearing ceremony is that each angel expresses his own mission, and their speeches are placed in N treasure boxes arranged in a circle. The boxes are numbered 1, 2, 3..., N-1, N clockwise. At first the angels stood by the treasure box numbered N. Each of them has a number in their hand, which represents the box in which their own speech is located in a clockwise direction from box 1. For example: there are 7 boxes, then if the number on TENSHI's hand is 9, then the box where her speech is located is the second one. Now the angels are looking for speeches according to the numbers in their hands, and they can speak first if they find them first. TENSHI found it all at once, so she first took the stage to swear: "I will lead everyone to open the door of NOI..." After TENSHI's oath ended, angels came to the stage to take the oath. There may be an angel who has been looking for her speech for a long time. It turns out that the number M in her hand is very large. She has been looking for a long time and can't find the treasure box she is looking for. Please help this angel find the number of the treasure box she is looking for.

enter

The first and second lines read positive integers N and M respectively, where N and M satisfy 2 ≤ N ≤ 10^8 and 2 ≤ M ≤ 10^1000

output

Ask for the number of the treasure box

Sample Input

Example 1

7
9

Example 2

11
108

Sample Output

Example 1

2

Example 2

9

Analysis of the meaning of the topic

This question is actually high-precision division and surplus, that is, crazy high-precision reduction, but because the size gap is too large, the size of N is 108, and the size of M is 101000. Violent reduction will be happy Time Limit Exceed, so we have to Using the shift method:
1234-12 we can use 1234-1200=34 first
Use 34-12=22 again
Finally use 22-12=10
The result is 10
Gorgeous code splitting line

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=1005;
char str1[maxn],str2[maxn];
int a[maxn],b[maxn],c[maxn];
void sub()
{
 int s,g=0;
    for(int i=maxn-1;i>0;i--)
      if (a[i]>=b[i]+g)
      {
       a[i]=a[i]-b[i]-g;
       g=0;
      }else
      {
       a[i]=10+a[i]-b[i]-g;
       g=1;
      }
}
bool comp(int a[],int b[])
{
 int i=0;
 while(a[i]==b[i]&&i<maxn)i++;
 if(i==maxn)return 1;
 return (a[i]>=b[i]);
}
void output()
{
 int i;
 i=1;
 while(a[i]==0&&i<maxn)i++;
 if(i==maxn)cout<<str1;
 else for(int j=i;j<maxn;j++)cout<<a[j];
}
void work()
{
   int j=1;
   while(comp(a,b))
   {
    j++;
    for(int i=2;i<maxn;i++)
    {
     b[i-1]=b[i];
     b[i]=0;
    }
   }
   while (j>0)
   {
    while(comp(a,b))sub();
    j--;
    for (int i=maxn-1;i>=1;i--) 
    {
     b[i]=b[i-1];
     b[i-1]=0;
    }
   } 
}
void init()
{
 memset(a,0,sizeof(a));
 memset(b,0,sizeof(b));
 memset(c,0,sizeof(c));
 scanf("%s%s",str1,str2);
 for(int i=0;i<strlen(str1);i++)
   b[maxn-strlen(str1)+i]=str1[i]-'0';
 for(int i=0;i<strlen(str2);i++)
   a[maxn-strlen(str2)+i]=str2[i]-'0';
 if(comp(a,b)==0||comp(b,a)==0)work();
}
int main()
{
 init();
 output();
 return 0;
}