Polycarpus participates in a competition for hacking into a new secure messenger. He's almost won.
Having carefully studied the interaction protocol, Polycarpus came to the conclusion that the secret key can be obtained if he properly cuts the public key of the application into two parts. The public key is a long integer which may consist of even a million digits!
Polycarpus needs to find such a way to cut the public key into two nonempty parts, that the first (left) part is divisible by a as a separate number, and the second (right) part is divisible by b as a separate number. Both parts should be positive integers that have no leading zeros. Polycarpus knows values a and b.
Help Polycarpus and find any suitable method to cut the public key.
The first line of the input contains the public key of the messenger — an integer without leading zeroes, its length is in range from 1 to 106 digits. The second line contains a pair of space-separated positive integers a, b (1 ≤ a, b ≤ 108).
In the first line print "YES" (without the quotes), if the method satisfying conditions above exists. In this case, next print two lines — the left and right parts after the cut. These two parts, being concatenated, must be exactly identical to the public key. The left part must be divisible by a, and the right part must be divisible by b. The two parts must be positive integers having no leading zeros. If there are several answers, print any of them.
If there is no answer, print in a single line "NO" (without the quotes).
116401024 97 1024
YES 11640 1024
284254589153928171911281811000 1009 1000
YES 2842545891539 28171911281811000
120 12 1
NO
题意:
给出一个长度为 n 的数字,后给出 a 和 b,问能否把这个数字分成两段,使之前半段能整除 a,后半段能整除 b。
思路:
数学。直接暴搜无疑会 TLE,从前面往后面扫的时候用 tap 标记这一位能否被 a 整除,边扫边还可以边计算能否被整除。之后从后面开始往前扫,但是从后面往前扫判断能否被整除就要看下公式了。因为
一个数 abc = (a X 100 + b X 10 + c),所以当模的时候就等于 a % M X 100 % M + b % M X 10 % M + c % M,所以从后面往前面扫的时候记录 10 的次方模就好,之后根据公式就可以算出了。
如果这位能被整除,且这一位的前一位 tap 值等于 1,则 break,输出两段数字即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; const int MAX = 1000005; char num[MAX]; int tap[MAX]; int main() { int a, b, len; memset(tap, 0, sizeof(tap)); scanf("%s", num); scanf("%d%d", &a, &b); len = strlen(num); int ans = 0; for (int i = 0; i < len; ++i) { ans *= 10; ans += num[i] - '0'; ans %= a; if (!ans) tap[i] = 1; } int temp = 0, in = 1; ans = 0; for (int i = len - 1; i >= 0; --i) { ans = (in * (num[i] - '0')) % b + ans; ans %= b; in = (in * 10) % b; if (!ans && num[i] != '0' && tap[i - 1]) { printf("YES\n"); temp = 1; for (int j = 0; j <= i - 1; ++j) { printf("%c", num[j]); } printf("\n"); for (int j = i; j < len; ++j) { printf("%c", num[j]); } printf("\n"); break; } } if (!temp) printf("NO\n"); return 0; }
相关推荐
hacking hacking hacking hacking
Hacking_ A 101 Hacking Guide,hack参考书,值的一看。
Web Hacking 101: How to Make Money Hacking Ethically By 作者: Peter Yaworski Pub Date: 2018 ISBN: n/a Pages: 255 Language: English Format: PDF Size: 10 Mb With a Foreword written by HackerOne Co-...
CAN总线脱敏数据集,包含韩国HCLR实验室所用的Car Hacking和Road两个数据集,包含的攻击模式有Fuzzy/Ddos/Spoofing等。可直接拿来做异常检测。基于该数据集的论文有Song, Hyun Min, Jiyoung Woo, and Huy Kang Kim. ...
比较新的Hacking攻防的概念和技术,具有很好的指导价值。
Title: Python Hacking Essentials Author: Earnest Wish Length: 214 pages Edition: 1 Language: English Publisher: CreateSpace Independent Publishing Platform Publication Date: 2015-04-01 ISBN-10: ...
Learn the basics of ethical hacking and gain insights into the logic, algorithms, and syntax of Python. This book will set you up with a foundation that will help you understand the advanced concepts ...
HackingTeam RCSAndroid sample
hacking Web learning book
Ethical Hacking & Countermeasures
google hacking
WiFi Hacking for Beginners - Learn Hacking by Hacking WiFi networks (2017) (Azw3)
WiFi Hacking for Beginners - Learn Hacking by Hacking WiFi networks (2017) (Epub)
《GoogleHacking技术手册》采纳了详尽的Google语法与工具。在发挥Google的最大搜索效用后,你又将如何反其道,让自己的信息无法被别人搜索到呢?只要你细细品读书中的讲解,顺着作者的逆向思维提示,便可轻松地找到...
Hacking Tutorials
Google Hacking
google hacking 技术手册
Web Hacking 101 中文版
Hacking with Swift