云南省城乡和住房建设厅网站,接家装活找哪个平台,女生做网站开发,上海企业制作网站参考链接#xff1a;求n#xff01;在m进制下末尾0的个数_.!零n,,m-CSDN博客
我们这里和参考链接不同
使用结构体去存储每个因数的信息
然后使用变量index作为索引#xff0c;其最终值为因数的个数
具体原理#xff1a;
例子1#xff1a;求9#xff01;在10进制下的…参考链接求n在m进制下末尾0的个数_.!零n,,m-CSDN博客
我们这里和参考链接不同
使用结构体去存储每个因数的信息
然后使用变量index作为索引其最终值为因数的个数
具体原理
例子1求9在10进制下的末尾的0的个数
思考1在10进制下出现0必须是质数2 与 5组合所以统计2和5作为因数出现了多少次取最小的数量就是答案
例子2求10在9进制下的末尾的0的个数
思考2在9进制出现0其必然是两个3组合起来才会在9进制出现0结尾所以统计所有因子里面各自出现的次数这里只有3然后 整除以 对应因子在进制9里面出现的次数 取最小的那一个值 即是答案
下面给出一个例题和题解
例题Contest1035 - NewOJ 2022 Contest 7 - New Online Judge (ecustacm.cn)
题解
#includeiostreamusing namespace std;
#define debug(x) cout#x : xendl;
typedef long long int ll;const int maxLine10010;
struct primeInfo {int nums;int counts;
};
void getPrime(int m);
void printPrimeArray(struct primeInfo arr[maxLine],int len);
int countDivision(int n,int p);struct primeInfo myPrime[maxLine];
// 记录数量和下标
int index0;
int res0x3f3f3f3f;
int main(){int n,m;
// cinnm;n20;m14; getPrime(m);
// printPrimeArray(myPrime,index);for(int i0;iindex;i){resmin(res,countDivision(n,myPrime[i].nums)/myPrime[i].counts);}coutres;return 0;
}
// 获取素数个数
void getPrime(int m){for(int i2;i*im;i){// 统计当前因数的个数和具体数值 while(m%i0){myPrime[index].numsi;myPrime[index].counts;m/i;}if(myPrime[index].counts!0) index; } //如果是合数 那么会在之前统计完//如果是质数 那么本身这个质因数统计不到if (m1) myPrime[index].numsm,myPrime[index].counts;
}
// 打印查看
void printPrimeArray(struct primeInfo arr[maxLine],int len){for(int i0;ilen;i){couti: arr[i].nums arr[i].countsendl;}
}
int countDivision(int n,int p){// 只要不包含1这个参数就一定会结束循环
// cout传入参数n pendl;int counts0;
// debug(counts);while(n0){countsn/p;n/p;}
// debug(counts);return counts;
}
中间用到了一点点判断因数范围的小技巧你发现了吗
