热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【2019.8.30】Za

Za2019.8.30SDOI2011计算器[BZOJ2242][luoguP2485]1、给定y、z、p,计算y^zmodp的值;2、给定y、z、p&

Za 2019.8.30

SDOI2011 计算器

[BZOJ2242] [luoguP2485]

1、给定y、z、p,计算y^z mod p 的值;

2、给定y、z、p,计算满足xy ≡z(mod p)的最小非负整数x;

3、给定y、z、p,计算满足y^x ≡z(mod p)的最小非负整数x。

第一个要求直接快速幂

第二个要求因为保证P为质数 直接费马小定理求逆元然后*z

第三个就是BSGS模板

==打的时候1mol错 要注意该加括号的就加括号 不要图简便啥的不加 然后就long long

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define Abs(x) ((x)<0?-(x):(x))
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
const int N&#61;10000&#43;5,M&#61;20000&#43;5,INF&#61;1e9&#43;7,inf&#61;0x3f3f3f3f;
int y,z,p;
template void rd(t &x){x&#61;0;int w&#61;0;char ch&#61;0;while(!isdigit(ch)) w|&#61;ch&#61;&#61;&#39;-&#39;,ch&#61;getchar();while(isdigit(ch)) x&#61;(x<<1)&#43;(x<<3)&#43;(ch^48),ch&#61;getchar();x&#61;w?-x:x;
}int qpow(int a,int b){int res&#61;1;while(b){if(b&1) res&#61;(ll)a*res%p;a&#61;(ll)a*a%p,b>>&#61;1;}return res;
}maphash;
int BSGS(){hash.clear();y%&#61;p,z%&#61;p;if(!y) return -1;int t&#61;(int)sqrt(p)&#43;1;for(int j&#61;0,val;j&#61;0&&i*t-j>&#61;0) return i*t-j;}return -1;
}void work2(){if(!(y%p)&&z%p) puts("Orz, I cannot find x!");else printf("%lld\n",(ll)qpow(y,p-2)*z%p);
}
void work3(){int ans&#61;BSGS();if(ans&#61;&#61;-1) puts("Orz, I cannot find x!");else printf("%d\n",ans);
}int main(){freopen("in.txt","r",stdin);int T,K;rd(T),rd(K); while(T--){rd(y),rd(z),rd(p);if(K&#61;&#61;1) printf("%d\n",(qpow(y,z))%p);else if(K&#61;&#61;2) work2();else work3();}return 0;
}

luogu4884 多少个1&#xff1f;

给定整数\(K\)和质数\(m\)&#xff0c;求最小的正整数\(N\)&#xff0c;使得 \(1111⋯1(N个1)\equiv K(mod\;m)\)

说人话&#xff1a;就是\(111...1111\; mod\;m &#61;K\)

\(1111⋯1(N个1)\)乘9得\(9999⋯9(N个9)\)\(&#43;1\)\(10^N\)

即求x使得\(10^x\equiv K*9&#43;1(mod\;m)\)

题解里的玄学快速乘

好像noip啥的不支持_int128 那就先不学了

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define Abs(x) ((x)<0?-(x):(x))
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
const int N&#61;10000&#43;5,M&#61;20000&#43;5,INF&#61;1e9&#43;7,inf&#61;0x3f3f3f3f;
ll y,z,p;
template void rd(t &x){x&#61;0;int w&#61;0;char ch&#61;0;while(!isdigit(ch)) w|&#61;ch&#61;&#61;&#39;-&#39;,ch&#61;getchar();while(isdigit(ch)) x&#61;(x<<1)&#43;(x<<3)&#43;(ch^48),ch&#61;getchar();x&#61;w?-x:x;
}ll mul(ll a, ll b){ll L &#61; a * (b >> 25LL) %p* (1LL <<25) %p;ll R &#61; a * (b & ((1LL <<25) - 1)) %p;return (L &#43; R) %p;
}ll qpow(ll a,ll b){ll res&#61;1;while(b){if(b&1) res&#61;mul(a,res)%p;a&#61;mul(a,a)%p,b>>&#61;1;}return res;
}maphash;
ll BSGS(){hash.clear();y%&#61;p,z%&#61;p;int t&#61;sqrt(p)&#43;1;for(int i&#61;0;i&#61;0&&(ll)i*t-j>&#61;0) return (ll)i*t-j;}return -1;
}int main(){freopen("in.txt","r",stdin);rd(z),rd(p);y&#61;10ll,z&#61;(z<<3)&#43;z&#43;1;ll ans&#61;BSGS();printf("%lld",ans);return 0;
}

exbsgs

银河英雄传说

重新打了一遍

带权并查集

#include
#include
#include
#include
#include
using namespace std;
#define Abs(x) ((x)<0?-(x):(x))
const int N&#61;30000&#43;5,M&#61;20000&#43;5,INF&#61;1e9&#43;7,inf&#61;0x3f3f3f3f;
int n,f[N];
template void rd(t &x){x&#61;0;int w&#61;0;char ch&#61;0;while(!isdigit(ch)) w|&#61;ch&#61;&#61;&#39;-&#39;,ch&#61;getchar();while(isdigit(ch)) x&#61;(x<<1)&#43;(x<<3)&#43;(ch^48),ch&#61;getchar();x&#61;w?-x:x;
}int d[N],sz[N];
int find(int x){if(x&#61;&#61;f[x]) return x;int rt&#61;find(f[x]);d[x]&#43;&#61;d[f[x]];return f[x]&#61;rt;
}
void Merge(int x,int y){f[x&#61;find(x)]&#61;y&#61;find(y),d[x]&#61;sz[y],sz[y]&#43;&#61;sz[x];
}int main(){freopen("in.txt","r",stdin);int T,x,y;char opt[5];rd(T);for(int i&#61;1;i<&#61;30000;&#43;&#43;i) f[i]&#61;i,sz[i]&#61;1;while(T--){scanf("%s",opt);rd(x),rd(y);if(opt[0]&#61;&#61;&#39;M&#39;) Merge(x,y);else{if(find(x)!&#61;find(y)) puts("-1");else printf("%d\n",Abs(d[x]-d[y])-1);}}return 0;
}

1930来的先生

卿卿吾愛&#xff0c;見字如晤&#xff1a;
  體無恙否&#xff1f;心安樂否&#xff1f;藝人之工作順利否&#xff1f;
  屈指算來&#xff0c;吾與汝七日未見&#xff0c;人言一日不見&#xff0c;如隔三秋&#xff0c;七日之長&#xff0c;煎熬甚苦。人生苦短如斯&#xff0c;言語小恚&#xff0c;便有這許多煎熬&#xff0c;若他日真作計較&#xff0c;又當何以自處&#xff1f;思來想去&#xff0c;日夜翻覆&#xff0c;更覺會日何短&#xff0c;隔日何長&#xff1f;憂思何繁&#xff0c;歡顏何驟&#xff1f;
  吾心愛汝&#xff0c;願見歡顏&#xff0c;恨吾怨吾&#xff0c;皆吾自取。當日失言&#xff0c;悔之不及。前日電訊致歉&#xff0c;卿定有閱之&#xff0c;閱而不復&#xff0c;非卿之過&#xff0c;是吾書未達意&#xff0c;辭未達情。游目天地&#xff0c;何以悅卿&#xff1f;雖天涯海角&#xff0c;卿所樂之&#xff0c;吾必往之&#xff0c;幽王癡情&#xff0c;敢笑薄之——此等甘辭蜜語&#xff0c;不能訴吾衷情于一二&#xff0c;卿心明澈&#xff0c;願可鑒之。
  論愛侶之屬&#xff0c;愛之尤甚&#xff0c;怨懟尤多&#xff0c;相思酷刑&#xff0c;甚于斧鉞。吾與卿七日未見&#xff0c;此卿卿于吾小懲大誡&#xff0c;吾必銘記於心&#xff0c;定無再犯。昨日歸家途中&#xff0c;見有春梅余香枝頭&#xff0c;衷情難表&#xff0c;癡意難訴&#xff0c;春意兩瓣&#xff0c;托于鴻雁。東君有意&#xff0c;顧惜芳春&#xff0c;卿卿當如東君&#xff0c;顧惜吾心。
  最后一张纸只有两行正楷大字&#xff1a;
  以上那些我知你必定看不懂&#xff0c;只看這最後兩句罷&#xff1a;我在你樓下等你&#xff0c;一起去閱江樓吃龍蝦。

[USACO]道路与航线

[BZOJ2200] [luoguP3008]

咕了&#xff01;

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef pairpii;
const int N&#61;25000&#43;5,M&#61;50000&#43;5,INF&#61;1e9&#43;7,inf&#61;0x3f3f3f3f;
int n,r,p,s,in[N];
template void rd(t &x){x&#61;0;int w&#61;0;char ch&#61;0;while(!isdigit(ch)) w|&#61;ch&#61;&#61;&#39;-&#39;,ch&#61;getchar();while(isdigit(ch)) x&#61;(x<<1)&#43;(x<<3)&#43;(ch^48),ch&#61;getchar();x&#61;w?-x:x;
}int hd[N],tt&#61;1;
struct edge{int v,w,nxt;}e[M<<2];
void add(int u,int v,int w){e[&#43;&#43;tt]&#61;(edge){v,w,hd[u]},hd[u]&#61;tt;
}int bl[N],cnt&#61;0;
vectorblo[N];
void dfs(int u){bl[u]&#61;cnt,blo[cnt].push_back(u);for(int i&#61;hd[u],v;i;i&#61;e[i].nxt)if(!bl[v&#61;e[i].v]) dfs(v);
}int dis[N];bool vis[N];
void topsort(){memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));queueQ;dis[s]&#61;0;//,Q.push((bl[s]))for(int i&#61;1;i<&#61;cnt;&#43;&#43;i) if(!in[i]) Q.push(i);priority_queue,greater >q;while(!Q.empty()){int k&#61;Q.front();Q.pop();for(int i&#61;0,x;idis[u]&#43;(w&#61;e[i].w)){dis[v]&#61;dis[u]&#43;w;if(bl[v]&#61;&#61;bl[u]) q.push((make_pair(dis[v],v)));}if(bl[u]!&#61;bl[v]&&!(--in[bl[v]])) Q.push(bl[v]);}}}
}int main(){freopen("in.txt","r",stdin);rd(n),rd(r),rd(p),rd(s);for(int i&#61;1,u,v,w;i<&#61;r;&#43;&#43;i) rd(u),rd(v),rd(w),add(u,v,w),add(v,u,w);for(int i&#61;1;i<&#61;n;&#43;&#43;i) if(!bl[i]) &#43;&#43;cnt,dfs(i);for(int i&#61;1,u,v,w;i<&#61;p;&#43;&#43;i)rd(u),rd(v),rd(w),add(u,v,w),&#43;&#43;in[bl[v]];topsort();for(int i&#61;1;i<&#61;n;&#43;&#43;i)if(dis[i]>&#61;1e9) puts("NO PATH");else printf("%d\n",dis[i]);return 0;
}

USACO cow relays

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define Abs(x) ((x)<0?-(x):(x))
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
typedef pairpii;
const int N&#61;1e6&#43;5,M&#61;200&#43;5,INF&#61;1e9&#43;7,inf&#61;0x3f3f3f3f;
int n,m,s,t,id[N];
template void rd(t &x){x&#61;0;int w&#61;0;char ch&#61;0;while(!isdigit(ch)) w|&#61;ch&#61;&#61;&#39;-&#39;,ch&#61;getchar();while(isdigit(ch)) x&#61;(x<<1)&#43;(x<<3)&#43;(ch^48),ch&#61;getchar();x&#61;w?-x:x;
}struct mp{int v[M][M];mp operator *(const mp &x)const{mp c;memset(c.v,inf,sizeof(c.v));for(int k&#61;1;k<&#61;id[0];&#43;&#43;k)for(int i&#61;1;i<&#61;id[0];&#43;&#43;i)for(int j&#61;1;j<&#61;id[0];&#43;&#43;j)c.v[i][j]&#61;Min(c.v[i][j],v[i][k]&#43;x.v[k][j]);return c;};
}a;int main(){
// freopen("in.txt","r",stdin);rd(n),rd(m),rd(s),rd(t);memset(a.v,inf,sizeof(a.v));for(int i&#61;1,u,v,w;i<&#61;m;&#43;&#43;i){rd(w),rd(u),rd(v);if(!id[u]) id[u]&#61;&#43;&#43;id[0];if(!id[v]) id[v]&#61;&#43;&#43;id[0];a.v[id[u]][id[v]]&#61;a.v[id[v]][id[u]]&#61;Min(a.v[id[u]][id[v]],w);}mp res&#61;a;--n;while(n){if(n&1) res&#61;res*a;a&#61;a*a,n>>&#61;1;}printf("%d",res.v[id[s]][id[t]]);return 0;
}

转:https://www.cnblogs.com/lxyyyy/p/11437376.html



推荐阅读
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • Java 中的 BigDecimal pow()方法,示例 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 在Linux系统中配置并启动ActiveMQ
    本文详细介绍了如何在Linux环境中安装和配置ActiveMQ,包括端口开放及防火墙设置。通过本文,您可以掌握完整的ActiveMQ部署流程,确保其在网络环境中正常运行。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
author-avatar
漫瀚聆静
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有