用 h 表明当前余数 即现阶段被除数
如果 h < b 需要补位 最后一位无数可补
最后需要去掉数字前面的0 但要考虑到商本身就是0的情况
#include using namespace std; int a[100005]; int ans[100005]; int main(){ long long b; string aa; cin>>aa>>b; int n=aa.length(); for(int i=0;i<n;i++){ a[i]=aa[i]-‘0’; } long long h=a[0]; int i=0; while(i<n){ if(h<b){ if(i==n-1) break; h*=10; h+=a[++i]; } ans[i]=h/b; h%=b; } int pd=1; for(int i=0;i<n;i++){ if(pd&&ans[i]0){ continue; }else if(ans[i]!=0){ pd=0; } cout<<ans[i]; } if(pd1) cout<<0; cout<<endl; cout<<h; return 0; }
题目描述
给定两个非负整数（不含前导 00） AA，BB，请你计算 A/BA/B 的商和余数。
输入格式
共两行，第一行包含整数 AA，第二行包含整数 BB。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤1000001≤A的长度≤100000,
1≤B≤100001≤B≤10000,
BB 一定不为 0
输入样例：
7
2
输出样例：
3
1
算法1
(高精度) O(n2)O(n2)
高精度除法要求求出商和余数，那我们的思路就是：把上一次的余数乘10，再加上当前位上的数，就是被除数，后面往C（答案）里压入这个数字除以bb，就可以得到商在这个位置上的数字。
时间复杂度
参考文献
C++ 代码
#include #include #include using namespace std; vector div(vector &A,int b,int &r){ // 取r的地址符，是为了更改r的值，方便后面输出余数 vector C; // 答案 r = 0; // 余数 for(int i = A.size() - 1;i >= 0;i --){ // 从最高位开始处理 r = r * 10 + A[i]; // 上一次的余数乘10，再加上当前位上的数，就是被除数 C.push_back(r / b); // 往C里压入这个被除数除b r %= b; // 计算余数 } reverse(C.begin(),C.end()); // 因为除法运算中从高位开始计算，而前导0都在顶部而不是底部，所以要翻转过来 while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前导0 return C; // 返回答案 } int main(){ string a; int b; cin>>a>>b; vector A; for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - ‘0’); // 倒序 int r; auto C = div(A,b,r); // 答案 for(int i = C.size() - 1;i >= 0;i --) cout<<C[i]; cout<<endl<<r<<endl; return 0; } 3
mex函数
将图上一个点可以到达的所有点的mex值组成一个集合
集合中不存在的最小自然数
此题用到的图
将终点状态（所有无法继续操作的石子数）的mex值设为0
起点为其中一堆石子的石子数
通过每种石子数可以到达的状态算出起点的mex值
就像这样：（样例的第3堆石子）
它的mex值就是：
所以mex(7)=0
必胜态和必败态
（这里只考虑一幅图）
当这幅图的起点的mex值为0
就是必败态
否则就是必胜态
原因：
从mex值的定义可以看出
当一个点的mex值为0
它一定只能到达mex值不为0的点
当一个点的mex值不为0
它一定可以到达mex值为0的点（双方都绝顶聪明，所以一定会到达mex值为0的点）
这时因为所有终点的mex值都是0
所以起点的mex值为零
说明先手一定走不到终点
所以是必败态
否则先手一定会走到终点
就是必胜态
解题方法
把n堆石子作为n幅图的起始点
每一步只能选择一幅图走一步
一个点的mex值为x
说明它可以到达mex值为0~x-1中任意一个自然数的点
所以可以从起点的mex值中拿取任意数值
有n个起点
这不就是经典nim游戏吗？！
所以把所有图起点的mex值亦或起来，就是结果
C++ 代码
#include #include #include<unordered_set> using namespace std; int f[10005],s[105],k,n; int sg(int x){ //用来求mex值 if(f[x]!=-1) //记忆化搜索，可以优化掉不少 return f[x]; unordered_set vis; //用来记录所有可以到达的点的mex值 for(int i=0;i<k;i++) if(x>=s[i]) //可以这么拿 vis.insert(sg(x-s[i])); for(int i=0;;i++) if(!vis.count(i)) return f[x]=i; //求出x点的mex值 } int main(){ memset(f,-1,sizeof f); scanf(“%d”,&k); for(int i=0;i<k;i++) scanf(“%d”,&s[i]); scanf(“%d”,&n); int ans=0; while(n–){ int now; scanf(“%d”,&now); ans^=sg(now); } puts(ans?“Yes”:“No”); return 0; }
