栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3753 Simple Equation

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3753 Simple Equation

#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>using namespace std;#define Zero(v) memset(v, 0, sizeof(v))typedef long long lld;const int maxn = 100010;const int MAX = 5555;const int INF = 1000000000;int fac1[100], fac2[100];int ret1[100], ret2[100];int fac[100], ret[100]; int prime[maxn];int tot;bool mk[maxn], OK;lld ansX, ansY;void init() {Zero(mk);for(int i=2; i*i<maxn; i++) {if(!mk[i]) {for(int j=i*i; j<maxn; j+=i) mk[j] = 1;}}tot = 0;for(int i=2; i<maxn; i++) {if(!mk[i]) prime[tot++] = i;}}void split(lld n, int* fac, int* ret, int &cnt) {lld m = n;for(int i=0; i<tot && prime[i]*prime[i]<=n; i++) {if(m%prime[i] == 0) {int tmp = 0;fac[cnt] = prime[i];while(m%prime[i] == 0) {m /= prime[i];tmp ++;}ret[cnt++] = tmp;}}if(m > 1) fac[cnt] = m, ret[cnt++] = 1;}lld modPow(int n, int m) {lld ret = 1;for(; m; m>>=1, n=n*n) {if(m&1) ret *= n;}return ret;}void dfs(lld A, lld B, lld M, lld cur, int step, int cnt) {if(step == cnt) {lld X = cur + B;lld Y = A*B/cur + A;if(X >= M) {if(!OK) {ansX = X;ansY = Y;}OK = true;if(X+Y < ansX+ansY) {ansX = X;ansY = Y;} else if(X+Y == ansX+ansY) {if(X < ansX) {ansX = X;ansY = Y;}}}return ;}for(int i=0; i<=ret[step]; i++) {dfs(A, B, M, cur*modPow(fac[step], i), step+1, cnt);}}void gao(lld A, lld B, lld M) {int cnt1 = 0, cnt2 = 0;split(A, fac1, ret1, cnt1);split(B, fac2, ret2, cnt2);int cnt = 0;fac[cnt] = 1;ret[cnt++] = 1;int i = 0, j = 0;while(i < cnt1 || j < cnt2) {if(i >= cnt1 && j >= cnt2) break;if(i >= cnt1) {fac[cnt] = fac2[j];ret[cnt] = ret2[j];cnt++; j++;if(j >= cnt2) break;continue;}if(j >= cnt2) {fac[cnt] = fac1[i];ret[cnt] = ret1[i];cnt++; i++;if(i >= cnt1) break;continue;}if(fac1[i] > fac2[j]) {fac[cnt] = fac2[j];ret[cnt] = ret2[j];cnt++; j++;continue;}if(fac1[i] < fac2[j]) {fac[cnt] = fac1[i];ret[cnt] = ret1[i];cnt++; i++;continue;}if(fac1[i] == fac2[j]) {fac[cnt] = fac1[i];ret[cnt] = ret1[i] + ret2[j];cnt++; i++; j++;continue;}}OK = false;dfs(A, B, M, 1, 0, cnt);if(OK) printf("%lld %lldn", ansX, ansY);else puts("No answer");}int main() {lld A, B, M;init();while(scanf("%lld%lld%lld", &A, &B, &M) != EOF) {gao(A, B, M);}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/376515.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号