P1619 解一元二次方程的烦恼网页链接P1619 解一元二次方程的烦恼题目背景JosephZheng 在写数学作业的预习。他往往使用 Casio 来帮忙解一元二次方程。但是 Casio 有一个问题就是当Δ b 2 − 4 a c \Deltab^2-4acΔb2−4ac为一个大素数或大合数时其开平方的结果会以小数显示而不是老师要求的二次根式形式。JosephZheng 很是苦恼一遇到这种情况就要手动解方程。一天他再也忍不住了于是打开了电脑编了一个 prime 程序……于是悲剧的 OIer 们就要跟着疯狂的 JosephZheng 一起编这个程序呵呵……题目描述废话少说给你一个大数N NN可能大于4 × 10 7 4 \times 10^74×107让你进行素性判断然后分解质因数。当然初中数学题不可能有大于4 × 10 7 4 \times 10^74×107的数让你判断素性因此超过范围的数可以忽略不计。为了让程序更加贴心JosephZheng 多了一些要求会在输入输出中给出具体情况。输入格式一个大数N NNN NN为非负整数其中这个数的各个数位之间可以插入各种符号包括负号和小数点等它们也需要被忽略例如1234 12341234可以为1 - 2alsdkjf3%##……#-4等。你需要在这一长串乱码中找出这个要判断的数。输入数据可能有多组如果读到一行没有数字的字串即结束。保证输入数据不超过100 100100组字符串长度不超过1000 10001000。输出格式在读入数据之前先输出Enter the number需要换行。然后输出Prime?问号后有一个空格但不要换行。如果是质数则输出Yes!否则输出No!。此时换行。若果是质数就 halt若是小于2 22的数则在输出No!后也 halt。若是合数则分解质因数。如果该数大于4 × 10 7 4 \times 10^74×107则输出The number is too large!然后 halt。否则分解质因数。输出结果的方式在输出样例中会详细给出。每组数据之间空一行。halt停止处理本组数据输入输出样例 #1输入 #14 eed输出 #1Enter the number Prime? No! 42^2 Enter the number输入输出样例 #2输入 #22 end输出 #2Enter the number Prime? Yes! Enter the number输入输出样例 #3输入 #3-1 adfs输出 #3Enter the number Prime? No! Enter the number输入输出样例 #4输入 #41234###24#13#1 hehe输出 #4Enter the number Prime? No! The number is too large! Enter the number输入输出样例 #5输入 #51.5 1 1234324123512343123 ~~~输出 #5Enter the number Prime? No! 153^1*5^1 Enter the number Prime? No! Enter the number Prime? No! The number is too large! Enter the number输入输出样例 #6输入 #612 halt输出 #6Enter the number Prime? No! 122^2*3^1 Enter the number说明/提示编这道题的 JosephZheng 有些无聊但是很考验基本功哦仔细审题水题一道。。。解题思路本题是字符串解析 素性判断 质因数分解的模拟题要求从一行含各种干扰字符的字符串中提取出十进制整数N NN并根据N NN的大小、是否质数以及是否超过阈值输出对应的提示或分解结果。由于数据组数最多100 100100每组字符串长度不超过1000 10001000且N ≤ 4 × 10 7 N \le 4\times 10^7N≤4×107采用简单的试除法即可高效完成素性判断与质因数分解。1. 问题等价转化输入解析每行字符串可能含有数字、字母、符号等只需提取所有十进制数字字符并按顺序拼接得到目标整数N NN。若一行中没有数字则视为输入结束。素性判断对于2 ≤ N ≤ 4 × 10 7 2 \le N \le 4\times 10^72≤N≤4×107判断其是否为质数。采用试除法枚举2 22到N \sqrt{N}N的整数若存在整除关系则N NN为合数否则为质数。质因数分解若N NN为合数且不超过4 × 10 7 4\times 10^74×107将其分解为质因数的幂乘积形式输出格式为Np1^e1*p2^e2*...。输出要求每组数据前输出Enter the number并换行接着输出Prime?注意问号后有空格不换行根据N NN的情况输出Yes!、No!或No!The number is too large!或质因数分解式每组数据结束后输出一个空行额外换行若读到没有数字的行结束整个程序。2. 算法实现循环读入并解析每次循环先输出Enter the number换行用getline读取一行字符串遍历字符串若字符为数字0~9则累加到整数numnum num * 10 digit并置flag1表示含有数字在累加过程中若num已经大于40000000则立即判断为“数过大”输出Prime? No!和The number is too large!并设置err1终止解析continue到下一组数据若整行无数字flag0则break结束程序。素性判断与输出若N 2 N2N2直接输出Prime? No!然后结束本组若isprime(N)为真输出Prime? Yes!否则输出Prime? No!以及质因数分解式。若N 4 × 10 7 N4\times 10^7N4×107则输出The number is too large!而非分解式但此情况已在解析阶段提前处理理论上不会再进入分解分支。质因数分解函数divi(x)从i 2 i2i2开始枚举若x % i 0 x\%i0x%i0统计该质因子的指数c cc不断除以i ii然后按格式输出i^c多个质因子之间用*分隔由于x xx在分解过程中不断减小循环条件ix最终会在x xx变为1 11后停止枚举范围不超过原 N \sqrt{\text{原}N}原N。3. 复杂度分析解析阶段每组字符串长度不超过1000 10001000时间复杂度O ( 1000 ) O(1000)O(1000)。素性判断试除法枚举到N \sqrt{N}N最坏N 4 × 10 7 N4\times 10^7N4×107约6325 63256325次循环属于常数级。质因数分解同样基于试除虽然代码循环写为ix但实际i ii最大只需到原 N \sqrt{\text{原}N}原N最坏约6325 63256325次完全可接受。总复杂度每组O ( L N ) O(L \sqrt{N})O(LN)L LL为字符串长度对于100 100100组数据总计约10 5 10^5105量级操作运行极快。总结本题主要考察字符串处理和基础数论算法。通过简单的线性扫描提取数字试除法完成素性判断与质因数分解注意输出格式空格、换行、空行和超限判断即可。代码结构清晰适合作为多组输入模拟题的练习。代码简要说明isprime(x)函数枚举2 22到x \sqrt{x}x若存在因子则返回false否则返回true。divi(x)函数从2 22开始试除记录每个质因子的指数按p^e顺序输出因子间用*连接。主循环输出Enter the number读入一行遍历提取数字并检查是否超过4 × 10 7 4\times 10^74×107若无数字则退出输出Prime?根据N NN的大小和素性分别输出Yes!、No!、分解式或超限提示每组后输出换行形成空行分隔。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;boolisprime(ll x){for(ll i2;isqrt(x)0.5;i)if(x%i0)return0;return1;}voiddivi(ll x){boolfi1;for(ll i2;ix;i)if(x%i0){ll c0;while(x%i0){c;x/i;}if(fi)fi0;elseprintf(*);printf(%lld^%lld,i,c);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);while(1){printf(Enter the number\n);ll num0,flag0,err0;string s;getline(cin,s);ll lens.size();for(ll i0;ilen;i){if(s[i]0s[i]9){flag1;numnum*10s[i]-0;}if(num40000000){printf(Prime? No!\nThe number is too large!\n\n);err1;break;}}if(!flag)break;if(err)continue;printf(Prime? );if(num2){printf(No!\n\n);continue;}if(isprime(num)){printf(Yes!\n\n);continue;}else{printf(No!\n%lld,num);divi(num);puts(\n);}}return0;}
)
