PAT复习自用——做题解和写过代码的搬运工

//数学专题：
/*
前言：构造性质，多枚举
*/
-------------------------------------------
//基本工具
typedef long long LL;
vector<int> res;
bool is_prime(int n);
LL gcd(LL a,LL b);


string str;
//当数字过长的时候，或者需要使用位置的性质使用方便
//1)    str.substr(pos,len);字符串求子串，处理数位问题很方便
//2)    int digit = stoi(str);字符转数字功能强大，支持double
bool check(char c);//判断合法的数字位
bool check(string str);//判断合法的数字串

//卡精度+1e-10  

-------------------------------------------
/*
（一）试除法思路
对应一种枚举的思路：顺序枚举，原数的性质在枚举方案后修改
*/
//PAT-1059  质因子，枚举因子，每次除因子，除干净，统计个数，按格式输出
//PAT-1096  连续因子 枚举因子的起始位置，试除，把答案存在vector里面，注意没有因子的情况，需要把自己push进去
******
bool is_prime()//试除法，判断是否是素数
{
    if(n<=1)return false;
    else if(n==2)return true;//容易遗漏 2是素数
    for(int i = 2;i*i<=n;i++)if(n%i==0)return false;
    return true;
}
//分解质因数
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

//分解因数递归问题：整数分解为若干项之和，由于使用dfs会重复记录一些路径，故使用set来消去重复解
//最后统一输出，而set又同时保证了输出序列是严格按照序列从小到大顺序输出的，在解决如何去重上花了一点功夫
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
using namespace std;
const int N = 10010;
int n, cnt = 0;
vector<int>path;
set<vector<int>>res;
void dfs(int x, int idx)
{
    if (x<0 || idx>n)return;
    if (x == 0)
    {
        res.insert(path);
        return;
    }
    path.push_back(idx);
    dfs(x - idx, idx);
    dfs(x - idx, idx + 1);
    path.pop_back();
    dfs(x, idx + 1);
}
int main()
{
    cin >> n;
    dfs(n, 1);
    for(auto c:res)
    {
        cout<<n<<"=";
        for(int i = 0;i<c.size();i++)
        {
            if(i)cout<<"+";
            cout<<c[i];
        }
        cnt++;
        if(cnt%4==0&&cnt!=1)cout<<endl;
        else if(cnt==res.size());
        else cout<<";";
    }
    return 0;
}
-------------------------------------------
/*
（二）最大公因数
模板题，通常题目中的一个环节，要求满足两个数的最大公因数性质
*/
//PAT-1081 有理数的和，PAT-1088 有理数运算
//该类问题处理难点在于格式化需要先同除公因数，然后考虑正负，分母是否为0，
//是否有整数,在通分的时候要判断是否溢出
********************
LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}
//通常用来计算有理数，或题意直接要求满足公因子的性质


-------------------------------------------
/*
（三）位和进制
对应按位枚举，按出现位置枚举，根据每一位确定统计值的大小，
进制问题掌握好进制的转化
难点是数位dp性质的挖掘
*/
//PAT-1104 数段之和 枚举方式为组合枚举，只要把连续区间描述好即可
//该连续区间包含的一位数（理解为位置）即是一个子结果
//进位制
//两个基本操作：数字按位向量化，数字字符串化
vector<int> get_vector(int n)
{
    vector<int>res;
    while(n)res.push_back(n%10),n/=10;
    reverse(res.begin(),res.end());
    return res;
}
string itos(int n)
{
    string res;
    while(n)res+=char(n%10+'0'),n/=10;//+'0'容易写错成 - 不要忘记除10
    reverse(res.begin(),res.end());//通常返回高位在前的数字，即常理数字
    return res;
}


-------------------------------------------
/*
进位制问题比较容易搞乱是正序数字位还是逆序，建议多调试一下
还要注意进制超过10的需要用字符串表示数，计算的时候可以都调整成10进制比较
*/
char change(int n)//数位扩展，用字符串表示
{
    if(n<=9)return (char)(n+'0');
    return (char)(n-10+'A');
}
******
//逆置有一个小技巧---vector<int> A(B.rbegin(),B.rend()); A此时是B的逆置


vector<int> change(int radix,int n)//按位返回radix进制下的数
{
    vector<int> d;
    while(n)d.push_back(n%radix),n/=radix;//按位存每一位的值，是逆置的
    return d;
}



int check_change(int radix,int n)//验证是逆置的
{
    int res = 0;vector<int> d;
    while(n)d.push_back(n%radix),n/=radix;//按位存每一位的值,是逆置的
    for(int i = d.size()-1;i>=0;i--)
        res = res*radix+d[i];
    return res;//res返回10进制的该数，验证为n
}



int reverse_change(int radix,int n)//radix进制翻转出来的数字
{
    int r = 0;
    while(n)
    {
        r = r*radix+n%radix;
        n/=radix;
    }
    return r;
}



//PAT-1015 可逆质数  注意素数是在十进制体系下的，本题本质就是进制转换

//PAT-1010 进制 比较困难 还考查了二分搜索的知识点
LL cal(string n,LL radix)//按照radix进制计算得到n的十进制值
{
    LL res = 0;
    for(auto c:n)
    {
        if((double)res*radix+get_(c)>1e16)return 1e18;
        res = res*radix+get_(c);
    }
    return res;
}
int main()
{
    int tag,radix;
    string N1,N2;
    cin>>N1>>N2>>tag>>radix;
    if(tag==2)swap(N1,N2);
    LL target = cal(N1,radix);
    LL l = 1,r = target+1;
    for(auto c:N2)
        l = (l>get_(c)+1)?l:get_(c)+1;//get_(c)+1  单位最大数字+1 = 最小进制
    while(l<r)
    {
        LL mid = (l+r)/2;
        if(cal(N2,mid)>=target)r = mid;
        else l = mid+1;
    }
    if(cal(N2,l)!=target)cout<<"Impossible"<<endl;
    else cout<<r<<endl;
    return 0;
}

-------------------------------------------
//其他数位问题
//1:回文
    for(int i = 0,j=num.size()-1;i<j;i++,j--)
        if(num[i]!=num[j])
        {
            flag=false;
            break;
        }
    if(flag)puts("Yes");
    else puts("No");
//Tips：回文问题可以通过reverse看是否是回文

-------------------------------------------
//2.数位dp
//PAT-1049 1的个数
/*
统计数字1在每一位出现的个数，更像是一个枚举问题
以所要求数为基准每次枚举时固定该位，令该位为1统计可能包含该位为1的情况
*/
int main()
{
    string digit;cin>>digit;int ans = 0;
    for(int i = 0;i<digit.size();i++)
    {
        int l = 0,r = 0;
        string left = digit.substr(0,i),right = digit.substr(i+1);
        if(left.size())l = stoi(left);
        if(right.size())r = stoi(right);
        if(digit[i]=='0')ans+=l*pow(10,right.size());
        //xxxx0xxxxx---xxxx'1'xxxxx   -> xxxx*10^5
        else if(digit[i]=='1')ans+=l*pow(10,right.size())+r+1;
        //xxxx1xxxxx---xxxx'1'xxxxx   -> xxxx*10^5+("=xxxx时")xxxxx+1
        else ans+=(l+1)*pow(10,right.size());
        //xxxx2xxxxx---xxxx'1'xxxxx   -> (xxxx+1)*10^5
    }
    cout<<ans<<endl;
    return 0;
}

-------------------------------------------
/*
（四）模拟问题
*/
//PAT-1112 坏掉的键盘  移动指针枚举（统计位数常用），只要位数不整除就没坏
//PAT-1116 C语言竞赛   模拟中使用了is_prime函数


//数学专题中的背包问题：PAT-1103 整数分解  K-P

-------------------------------------------
/*
（五）高精度
思路是将每一个幂次（理解成位）存储在数组中的一个位置
类似多项式的存储模式
*/
double a[N],b[N];
-------------------------------------------
//乘法
for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            c[i + j] += b[i] * a[j];
-------------------------------------------
//加法
for(int i = 0;i<N;i++)
    c[i] = a[i]+b[i];
-------------------------------------------
//输出非零元素的个数，以及多项式的各位
int k = 0;
for (int i = 0; i < N * 2; i ++ )
    if (c[i])
        k ++ ;

cout << k;
for (int i = N * 2 - 1; i >= 0; i -- )
    if (c[i])
        printf(" %d %.1lf", i, c[i]);
-------------------------------------------
//PAT-1023 趣味数字是将其向量化，做一次乘2运算，
//因此手动一次加法，模拟进位

vector<int> ddouble(string digit)
{
    vector<int>res;int over = 0;
    reverse(digit.begin(),digit.end());
    for(auto c:digit)
    {
        int now = over+(c-'0')*2;
        res.push_back(now%10);
        over = now/10;
    }
    if(over)res.push_back(over);
    reverse(res.begin(),res.end());
    return res;
}
//该题使用小技巧 sort判断是否为shuffle序列
sort(ans.begin(),ans.end());
sort(before.begin(),before.end());
if(ans==before)puts("Yes");
else puts("No");

---------------//算法进阶指南
//质数距离
/*
考查线性筛法：
关于线性筛法的博客：https://www.jianshu.com/p/f16d318efe9b
trick:  上取整：(a+b-1)/b  找到大于a的最小b的倍数等于  (a+b-1)/b * b;



L,R的范围很大，但R-L范围很小，可以预处理sqrt(R)内的素数。
对于每个素数p，把[L,R]范围中能被p整除的数标记，即标记i*p(ceil(L/p)<=i<=floor(R/p))。
[L,R]中没被标记的数就是素数，相邻两两进行比较求答案即可。
*/
//普通筛法
******
//素数筛法--可以提高试除法10倍速度，只试除1~根号x中的质数，而质数有logn个
//筛法和试除法的本质区别就在于筛法是求一个区间内的所有质数，而试除法是判断一个数是不是质数的方法
const int N = 1010, M = 40000;
bool st[M];
int primes[M], cnt;//存储第cnt个质数，cnt是当前下标
void init()
{
    cnt = 0;
    for (int i = 2; i < M; i ++ )
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            for (int j = i * 2; j < M; j += i)//这一步筛的效率较低，重复计算过多
                st[j] = true;
        }
}
bool check(int x)
{
    for (int i = 0; primes[i] <= x / primes[i]; i ++ )
        if (x % primes[i] == 0)
            return false;
    return true;
}
/*
普通筛法缺点
存在重复筛选，比如6既可以被2筛掉，又可以被3筛掉。
原因：任意一个整数可以写成一些素数的乘积 n=p1^a * p2^b * p3^c，其中p1<p2<p3，这样这个数n就能被p1,p2和p3筛掉
解决方法：按照一个数的最小素因子筛去(也就是这里的p1)就可以啦，这也就有了线性筛素数
*/
//线性筛：https://www.acwing.com/activity/content/code/content/21916/
const int N = 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    memset(st, false, sizeof st);
    cnt = 0;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )//确保不会越界
        {
            st[primes[j] * i] = true;//素因子之积被标记为合数
            if (i % primes[j] == 0) break;//比如4*3就不会在i等于4的时候筛去，因为4*3可写成6*2，只会i = 6时筛去
        }
    }
}
/*
线性筛的优点：
优点：没有重复筛同一个数
原因：按照一个数的最大素因子筛选，比如6只按3筛去
*/



---------------
//阶乘的质因子分解：https://www.acwing.com/activity/content/code/content/21919/
/*
结合阶乘的性质，质数分解的升级版，首先优化了枚举方式，只枚举质数，然后，次数就是数1~n内p的出现个数
从小到大枚举p，考虑1-n中包含了多少个p的倍数,如5! = 2*3*4*5   2和4是2的倍数，因此2的指数至少是2个(2 = 5/2)
然后我们发现漏了4中还多了一个2的指数(4 = 2^2，而刚刚只是把2的一次方给算上了)因此要加5/2^2=1(也就是数字4)
n! = 1*2*3*...*n 因此我们可以用n/p+n/p^2+n/p^3...表示次数
*/
const int N = 1000100;
bool st[N];
int cnt,primes[N];
void get_primes(int n)
{
    for(int i = 2;i<=n;i++)
    {
        if(!st[i])primes[cnt++] = i,st[i] = true;
        for(int j = 0;j<cnt&&primes[j]<=n/i;j++)
        {
            st[primes[j]*i] = true;
            if(i%primes[j]==0)break;
        }
    }
}
int main()
{
    int n;cin>>n;
    get_primes(n);
    for(int i = 0;i<cnt;i++)
    {
        int p = primes[i];
        int s = 0;
        for(int j = p;j<=n;j*=p)
        {
            s+=n/j;
            if(j>n/p)break;
        }
        cout<<p<<" "<<s<<endl;
    }
    return 0;
}


--------------
/*
反素数：
首先了解因数的性质：将一个数写成质因子的幂次乘积形式
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
*/
----------
/*
快速幂---位运算

*/
#include<iostream>
using namespace std;
int main()
{
    int a,b,p;
    cin>>a>>b>>p;
    int res= 1%p;
    while(b)
    {
        if(b&1)res = 1ll*res*a%p;
        a = 1ll*a*a%p;
        b>>=1;
    }
    cout<<res<<endl;
    return 0;
}

--------------------------------------
//分治法求等比数列的和（因为如果使用等比数列求和公式，无法对除法进行mod运算）



//高精度模板
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct BigNum
{
    int num[2100];
    int len;
    BigNum() 
    {
        memset(num, 0, sizeof num);
        len = 0;
    }
};
void print(BigNum x)
{
    for (int i = x.len-1; i >= 0; i--)
        cout << x.num[i];
    if (x.len == 0)cout << 0;
    cout << endl;
}
BigNum Add(BigNum a, BigNum b)
{
    BigNum c;
    c.len = max(a.len, b.len);
    for (int i = 0; i < c.len; i++)
        c.num[i] = a.num[i] + b.num[i];
    for (int i = 0; i < c.len; i++)
    {
        c.num[i + 1] += c.num[i] / 10;
        c.num[i] %= 10;
    }
    if (c.num[c.len])c.len++;
    return c;
}
BigNum Mul_low(BigNum a, int b)
{
    BigNum c;
    c.len = a.len;
    for (int i = 0; i < c.len; i++)
        c.num[i] = a.num[i] * b;
    for (int i = 0; i < c.len; i++)
    {
        c.num[i + 1] += c.num[i] / 10;
        c.num[i] %= 10;
    }
    if (c.num[c.len - 1])c.len++;
    while (c.len > 0 && !c.num[c.len - 1])c.len--;
    return c;
}
BigNum Sub(BigNum a, BigNum b)
{
    BigNum c;
    c.len = max(a.len, b.len);
    for (int i = 0; i < c.len; i++)
        c.num[i] = a.num[i] - b.num[i];
    for (int i = 0; i < c.len; i++)
    {
        if (c.num[i] < 0)
        {
            c.num[i + 1]--;
            c.num[i] += 10;
        }
    }
    if (!c.num[c.len - 1])c.len--;
    return c;
}
BigNum Mul(BigNum a, BigNum b)
{
    BigNum c;
    c.len = a.len + b.len;
    for (int i = 0; i < a.len; i++)
        for (int j = 0; j < b.len; j++)
            c.num[i + j] = a.num[i] * b.num[j];
    for (int i = 0; i < c.len; i++)
    {
        c.num[i+1] += c.num[i] / 10;
        c.num[i] %= 10;
    }
    while (c.len > 0 && !c.num[c.len - 1])c.len--;
    return c;
}
BigNum Div(BigNum a, int b)
{
    BigNum c;
    int t = 0;
    c.len = a.len;
    for (int i = c.len - 1; i >= 0; i--)
    {
        t = t * 10 + a.num[i];
        c.num[i] = t / b;
        t %= b;
    }
    while (c.len > 0 && !c.num[c.len - 1])c.len--;
    return c;
}

//练习——高精度除法——整除光棍
#include<iostream>
using namespace std;
struct BigNum
{
    int num[1001];
    int len;
};
bool calc(int size, int x)
{
    BigNum c;
    c.len = size;
    int t = 0;
    for (int i = 0; i < size; i++)c.num[i] = 1;
    for (int i = c.len - 1; i >= 0; i--)
    {
        t = t * 10 + c.num[i];
        c.num[i] = t / x;
        t %= x;
    }
    if (t == 0)return true;
    else return false;
}
int main()
{
    int x;
    cin >> x;
    int k = 1;
    while (!calc(k, x))k++;
    BigNum temp,r;
    temp.len = k, r.len = k;
    for (int i = 0; i < k; i++)temp.num[i] = 1;
    int t = 0;
    for (int i = k-1; i>=0; i--)
    {
        t = t * 10 + temp.num[i];
        r.num[i] = t / x;
        t %= x;
    }
    while (r.len > 0 && !r.num[r.len-1])r.len--;
    for (int i = r.len-1; i>=0; i--)
        cout << r.num[i];
    cout << " ";
    cout << k << endl;
    return 0;
}

//矩阵乘法
#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N],c[N][N];
int main()
{
    int x, y, z, w;
    cin >> x >> y;
    for (int i = 0; i < x; i++)
        for (int j = 0; j < y; j++)
            cin >> a[i][j];
    cin >> z >> w;
    for (int i = 0; i < z; i++)
        for (int j = 0; j < w; j++)
            cin >> b[i][j];
    if (z != y)
    {
        printf("Error: %d != %d", y, z);
        return 0;
    }
    else
    {
        for (int i = 0; i < x; i++)
            for (int j = 0; j < w; j++)
                for (int k = 0; k < y; k++)
                    c[i][j] += a[i][k] * b[k][j];
    }
    cout << x << " " << w << endl;
    for (int i = 0; i < x; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cout << c[i][j];
            if (j != w - 1)cout << " ";
        }
        cout << endl;
    }
    return 0;
}


//to be continued......










----------------------------------
//近年真题
//2019浙大考研上机考试-Conway's Conjecture------factorize问题
18=2×3^2
232=2^3*29
2329=17×137
17137 is a prime.
//观察上述序列可以看出，本题需要分解质因子，然后组合的要求是指数=1时不计入,!=1时计入
#include<iostream>
using namespace std;
string conway(int n)
{
    string ans;
    for(int i = 2;i*i<=n;i++)
        if(n%i==0)
        {
            int cnt = 0;
            ans+=to_string(i);
            while(n%i==0)n/=i,cnt++;
            if(cnt!=1)ans+=to_string(cnt);
        }
    if(n>1)ans+=to_string(n);
    return ans;
}
bool is_prime(int n)
{
    if(n<=1)return false;
    if(n==2)return true;
    for(int i = 2;i*i<=n;i++)
        if(n%i==0)return false;
    return true;
}
int main()
{
    int n;cin>>n;
    string res = conway(n);
    cout<<res<<endl;
    if(is_prime(stoi(res)))puts("Yes");
    else puts("No");
    return 0;
}