#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string.h>

using namespace std;
const int N = 1010;
char s[N];
int f[N][N];
int main()
{
    cin>>s;
    int n = strlen(s);
    for(int len = 1; len <= n; len++)
    {
         for(int l = 0; l + len - 1 < n;l++)
         {
             int r = l + len -1;
             if(l == r) f[l][r] = 1;
             else
             {
                  if(s[l] == s[r] ) f[l][r] = f[l+1][r-1] + 2;

                  if(f[l][r-1] > f[l][r]) f[l][r] = f[l][r-1];
                  if(f[l+1][r] > f[l][r]) f[l][r] = f[l+1][r];
             }
         }
    }

    int res = n - f[0][n-1];
    cout<<res;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;
const int N = 110;

int f[N][N],n,k;

int main()
{
    cin>>n>>k;

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    for(int i = 1;i <= n;i++)
    {
        int w;
        scanf("%d",&w);

        for(int j = 0;j < k;j++)
        {
            f[i][j] = max(f[i-1][j], f[i-1][(j + k - w % k) % k] + w);
        }
    }

    cout<<f[n][0]<<endl;

    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;
const int N = 12;
int f[N][N];
int main()
{
    int t,n,m;

    cin>>t;

    while(t--)
    {
        cin>>m>>n;

        f[0][0] = 1;

        for(int i = 0;i <= m;i++)
        {
            for(int j = 1;j <= n;j++)
            {
                f[i][j] = f[i][j-1];
                if(i >= j)
                {
                    f[i][j] += f[i-j][j];
                }
            }
        }

        printf("%d\n",f[m][n]);
    }

    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;
const int N = 110,M = 1 << 20;

int n,m,k;
vector<int> col[N];
int log2[M];

int lowbit(int x)
{
    return x & -x;
}

int h(int state)
{
    int res = 0;
    for(int i = (1<<m) - 1 - state;i;i -= lowbit(i))
    {
        int c = log2[lowbit(i)];
        res++;
        for(auto t : col[c]) i &= ~t;
    }
    return res;
}
bool dfs(int depth, int state)
{
    if(!depth || h(state) > depth) return state == (1 << m) -1;

    int t = -1;
    for(int i = (1 << m) - 1 - state; i ;i -= lowbit(i))
    {
        int c = log2[lowbit(i)];
        if(t == -1 || col[t].size() > col[t].size()) t = c;
    }

    for(auto row : col[t])
       if(dfs(depth - 1,state | row))
          return true;

    return false;
}
int main()
{
    cin>>n>>m>>k;

    for (int i = 0; i < m; i ++ ) log2[1 << i] = i;
    for(int i = 0;i < n;i++)
    {
        int state = 0;
        for(int j = 0;j < k;j++)
        {
            int c;
            cin>>c;
            state |= 1 << c-1;
        }

        for(int j = 0;j < m;j++)
           if(state>>j & 1)
              col[j].push_back(state);
    }
    for (int i = 0; i < m; i ++ )
    {
        sort(col[i].begin(), col[i].end());
        col[i].erase(unique(col[i].begin(), col[i].end()), col[i].end());
    }

    int depth = 0;
    while(depth <= m && !dfs(depth,0)) depth++;

    if(depth > m) cout<<-1<<endl;
    else
    {
        cout<<depth<<endl;
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

string str;
int k;
int dfs()
{
    int res = 0;
    while(k<str.size())
    {
        if(str[k] == '(')
        {
            k++;
            res += dfs();
            k++;
        }
        else if(str[k] == '|')
        {
            k++;
            res = max(res, dfs());
        }
        else if(str[k] == ')') break;
        else
        {
            k++;
            res++;
        }
    }

    return res;
}

int main()
{
    cin>>str;

    int res = dfs();

    cout<<res;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
typedef long long LL;

LL a,b,c,k;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

int main()
{
    while(cin>>a>>b>>c>>k, a||b||c||k )
    {
        k = 1ll << k;
        LL x,y;
        LL d = exgcd(c, k, x, y);

        if((b-a) % d) cout<<"FOREVER"<<endl;
        else
        {
            x *= (b-a)/d;
            k /= d;
            cout<<(x % k + k)%k<<endl;
        }
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
typedef long long LL;
const int N = 110;
int n;
LL x[N],a[N],b[N];
LL gcd(LL a,LL b)
{
    return b ? gcd(b , a%b) : a;
}

LL gcd_sub(LL a, LL b)
{
    if(a < b) swap(a,b);
    if(b == 1) return a;
    return gcd_sub(b,a/b);

}
int main()
{
    cin>>n;
    for(int i = 0;i < n;i++) cin>>x[i];

    sort(x,x+n);

    int cnt = 0;
    for(int i = 1;i < n;i++) 
    {
        if(x[i] != x[i-1])
        {
            LL d = gcd(x[i],x[0]);
            a[cnt] = x[i] / d;
            b[cnt] = x[0] / d;
            cnt++;
        }
    }

    LL up = a[0],down = b[0];
    for(int i = 1; i < cnt;i++)
    {
        up = gcd_sub(up,a[i]);
        down = gcd_sub(down,b[i]);
    }

    cout<<up<<'/'<<down<<endl;

    return 0;
}

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x = 1;
y = 0;
return a;
}
LL d = exgcd(b , a % b , y , x);
y -= a / b * x;
return d;
}
int main()
{
int T;
cin>>T;
LL n,d,x,y,a,b;
while(T–)
{
cin>>n>>d>>x>>y;

    int gcd = exgcd(n , d , a , b);

    if((y-x) % gcd != 0) puts("Impossible");
    else
    {

        b *= (y-x)/gcd;
        n /= gcd;

        cout<<(b % n + n) % n<<endl;
    }
}
return 0;

}
```

每个大于1的数都能分解成多个质数的乘积

x = p1^a1 * p2^a2 * p3^a3…;

由上可得出每个数的公约数的和公式

s = (1 + p1^1 +…+ p1^a1) * (1 + p2^1 +…+ p2^a2) * … * (1 + pn^1 +…+ pn^an);

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
int s;
const int N = 50000;
int prime[N];
bool st[N];

int len,cnt;

int ans[N];

void get_prime(int n)
{
    for(int i = 2;i <= n;i++)
    {
        if(!st[i]) prime[cnt++]= i;
        for(int j = 0; prime[j] * i<= n;j++)
        {
            st[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}
bool is_prime(int x)
{
    if(x < N) return !st[x];
    for(int i = 0;prime[i] <= x/prime[i];i++)
    {
        if(x % prime[i] == 0) return false;
    }
    return true;
}
void dfs(int last, int num,int s)
{
    if(s == 1)
    {
       ans[len++] = num;
       return ;
    }

    if(s-1 > (last < 0? 1 : prime[last]) && is_prime(s-1))
       ans[len++] = num * (s-1);

    for(int i = last + 1;prime[i] < s / prime[i]; i++)
    {
        int p = prime[i];
        for(int j = 1 + p, t = p;j <= s; t*=p,j += t)
            if(s % j == 0)
               dfs(i, num * t, s/j );
    }
}
int main()
{
    get_prime(N-1);

    while(cin >> s)
    {
        len = 0;

        dfs(-1,1,s);

        cout<<len<<endl;

        if(len)
        {
            sort(ans,ans + len);
            for(int i = 0;i < len;i++)
            {
                cout<<ans[i]<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}