【UOJ#74】【UR #6】破解密码

向右看齐 2021-11-16 09:32 281阅读 0赞

# 【UOJ\#74】【UR \#6】破解密码 #

## 题面 ##

[UOJ][]

## 题解 ##

发现这个过程是一个字符串哈希的过程。  
把第一位单独拿出来考虑，假设这个串是\\(p+S\\)，旋转后变成了\\(S+p\\)。  
其哈希值分别是：\\(p\*26^\{|S|\}+hash(S)\\)和\\(hash(S)\*26+p\\)。  
那么\\(h\[i\]\*26-h\[i+1\]=p\*26^\{n\}-p\\)  
那么这里显然可以直接把\\(p\\)给解出来。  
这样子就可以还原出每一位了。  
注意到特殊情况：\\(26^n-1\\)没有逆，此时无法直接计算。  
然而注意到\\(26^n=1\\)，所以得到右边是\\(0\\)  
此时\\(h\[i\]\*26=h\[i+1\]\\)，此时和\\(p\\)无关了，所以任意一个能满足\\(h\[0\]\\)的串都是合法的。  
那么直接把\\(h\[0\]26\\)进制分解就行啦。

#include<iostream>
    #include<cstdio>
    using namespace std;
    #define MAX 100100
    inline int read()
    {
        int x=0;bool t=false;char ch=getchar();
        while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
        if(ch=='-')t=true,ch=getchar();
        while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
        return t?-x:x;
    }
    int n,MOD,h[MAX],a[MAX];
    int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}
    int main()
    {
        n=read();MOD=read();int inv=fpow(fpow(26,n)-1,MOD-2);
        for(int i=0;i<n;++i)h[i]=read();h[n]=h[0];
        if(inv)for(int i=0;i<n;++i)putchar(1ll*(26ll*h[i]%MOD+MOD-h[i+1])%MOD*inv%MOD+97);
        else
        {
            for(int i=n-1;~i;--i)a[i]=h[0]%26,h[0]/=26;
            for(int i=0;i<n;++i)putchar(a[i]+97);
        }
        puts("");
        return 0;
    }

转载于:https://www.cnblogs.com/cjyyb/p/11087977.html

[UOJ]: http://uoj.ac/problem/74

发表评论取消回复

表情：

评论列表（有 0 条评论，281人围观）

还没有评论，来说两句吧...

相关阅读

相关 uoj#209【UER #6】票数统计

[题目][Link 1] 做UER的A题涨信心首先我们注意到这个所谓的至少有一条正确在\\(x\\)和\\(y\\)不相等的时候非常弱，当\\(x<y\\)时，只有可能是

小咪咪/ 2023年10月11日 11:20/ 0 赞/ 24 阅读

相关 uoj33 【UR #2】树上GCD

[题目][Link 1] 大致是长剖+\\(\\rm dsu\\ on\\ tree\\)的思想先做一个转化，改为对于\\(i\\in\[1,n-1\]\\)求出有多少个

冷不防/ 2023年10月11日 05:22/ 0 赞/ 28 阅读

相关 uoj192 【UR #14】最强跳蚤

[题目][Link 1] 和成爷达成一致，被卡随机的话就是过了考虑一个完全平方数的所有质因子次幂一定是偶数，于是对于每一条边我们都只保留其出现次数为奇数的质因子注意到

曾经终败给现在/ 2023年10月11日 05:14/ 0 赞/ 9 阅读

相关【UR #6】懒癌

Problem Description 你绞尽脑汁也没有解开智商锁给的迷题，只见哐地一下门就开了：“您与锁的主人智商一致。” 于是你们窃取了大量内部资料，最后端掉

本是古典何须时尚/ 2023年08月17日 15:48/ 0 赞/ 104 阅读

相关 6位数密码C++破解程序，并附上时间

![Center][]![Center 1][] 今天在看hash函数对于数字或字符进行加密的知识，有感而发就写了一个C++破解6位数数字密码的程序，程序很简单，

超、凢脫俗/ 2022年09月25日 04:14/ 0 赞/ 236 阅读

相关破解密码之破解数字+字母密码篇----java实现

import java.lang.; public class PojiePassword{ static String real="ZYXLXP

ゝ一纸荒年。/ 2022年05月30日 10:23/ 0 赞/ 548 阅读

相关破解Linux密码

1、重启linux按e、再按e会出现如下图所示、上下选第二个。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR

客官°小女子只卖身不卖艺/ 2022年04月08日 11:38/ 0 赞/ 497 阅读

相关【UOJ#74】【UR #6】破解密码

【UOJ\74】【UR \6】破解密码题面 [UOJ][] 题解发现这个过程是一个字符串哈希的过程。把第一位单独拿出来考虑，假设这个串是\\(p+

向右看齐/ 2021年11月16日 09:32/ 0 赞/ 282 阅读

相关【UOJ#48】【UR #3】核聚变反应强度（质因数分解）

【UOJ\48】【UR \3】核聚变反应强度（质因数分解）题面 [UOJ][] 题解答案一定是\\(gcd\\)除掉\\(gcd\\)的最小质因子。

谁践踏了优雅/ 2021年11月16日 09:32/ 0 赞/ 280 阅读

相关 CentOS6 破解登录密码

1、重启服务器，在倒数读秒的时候按任意键，就会出现如下界面 ![1336432-20190714203833455-806263771.png][] 2、按e进入gr

绝地灬酷狼/ 2021年11月02日 03:42/ 0 赞/ 462 阅读