UVA1635-唯一分解定理的基本应用2
2024-10-08 08:18:42
原题:https://vjudge.net/problem/UVA-1635
这是一个极其典型的“从素因子角度出发”的题目,下面是我的代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std; const int maxn = 1e5 + ;
int md[],mz[];
int ans[maxn];
int n,m,lenth;
int c[]; bool check(int n,int i)
{
int x=n-i;
int y=i;
for(int k=;k<lenth;k++)
{
int p=md[k];
while(x%p==)
{
x/=p;
c[k]++;
}
while(y%p==)
{
y/=p;
c[k]--;
}//上下两个循环不能合并,因为这是一个递增积累过程,
}//也正因如此才需要额外开辟一个数组c.
for(int k=;k<lenth;k++)
if(c[k]<mz[k])return false;
return true;
} int factor()
{//用来分解m
memset(md,,sizeof(md));
memset(mz,,sizeof(mz));
int c=m,cur=;
int p=sqrt(c);
for(int i=;i<=p;i++)
{
bool ok=false;
while(c%i==)
{
md[cur]=i;
mz[cur]++;
c/=i;
ok=true;
}
if(ok)cur++;
if(c==)break;
}
if(c>)md[cur]=c,mz[cur]=,cur++;
return cur;
} int main()
{
//freopen("input.txt","r",stdin);
//freopen("text.txt","w",stdout);
while(cin>>n>>m)
{
lenth=factor();//一开始忘记了记录lenth
int cnt=;
memset(c,,sizeof(c));
//
for(int i=;i<n-;i++)
if(check(n,i))ans[cnt++]=i+;
printf("%d\n",cnt);
for(int i=;i<cnt;i++)
{
if(i>)printf(" ");
printf("%d",ans[i]);
}
printf("\n");
}
return ;
}
最新文章
- 数据结构:二叉查找树(C语言实现)
- 使用Ruby来实现批量更新AD中字段
- Android Activity launchMode研究
- mysql存储过程详细教程
- ng-repeat &;&; ng-options的故事
- 能分析压缩的日志,且基于文件输入的PYTHON代码实现
- 读jQuery源码 jQuery.data
- Oracle笔记之对象权限与系统权限总结
- cdlinux可以安装在c盘
- 腾讯AI开放平台的使用
- 18.21 关键字extern
- React组件的State
- Iris Classification on Tensorflow
- Angular简介与程序架构
- mysql的root的权限被控制无法授权
- UVa 11082 Matrix Decompressing - 网络流
- mapreduce程序的按照key值从大到小降序排列
- easyUI制作slider小滑块,可拖动和精确输入
- Java中的IO流(四)
- 设计模式之笔记--单例模式(Singleton)
热门文章
- CassandraAppender - distributed logging,分布式软件logback-appender
- 自学Java第四章——《数组》
- 用javascript修改html元素的class
- MPlayer参数使用介绍(部分)(中文)
- Codeforces Round #470 (Div. 2) A Protect Sheep (基础)输入输出的警示、边界处理
- Window下,Jenkins忘记密码解决方法
- lwip的内存管理
- aliyun---经过LB到后端k8s压测超时的问题
- Linux Firewalld用法及案例
- H5浏览器强制手机横屏