2012-11-22 08:25:32Morris
[ZJ][規律] a568. ISSC 2012- problem B
內容 ：
給定一個數字N，代表這個數字有2N位數，
我們先定義 Good number
當我們把一個數字切一半
( ez. 1981 切一半變成 19 和 81 )
當他切一半後的兩個數字都可以整除原本的數字時，
這個數字就是Good Number
例如 2244
22 可以整除 2244 , 44 也可以整除 2244
所以2244是一個Good number
本題是要你找2N位的數字中有幾個Good number
噢~ 任何Good number 分成的左右兩半都不可以有數字0
ex 2200 ( 除以0是不合法的 )
輸入說明
：
多筆輸入
每行有兩個正整數N, M
1 <= N <= 7000007 , 2 <= M <= 10000 ( 原本題目是只有到8 )
輸出說明
：
請輸出位數為2N的Good number 有幾個
，因為答案可能很大，請輸出 modulo M 的結果
範例輸入
：
1 25 2 150
範例輸出 ：
14 5
提示
：
1. 70% 分數的測資 N <= 5 , M <= 100
2. 25% 分數的測資 N <= 8 , M <= 1000
3. 4 % 分數的測資 N <= 10 , M <= 10000
4. 1 % 分數的測資 N <= 7000007 , M <= 10000
hint : please use brute force if you want to get 95 points
PS. 時間開到最寬了~
出處
：
ISSC 2012
(管理：stanley17112000)
暴搜幾筆之後找規律即可
14
155
1575
15750
157500
/**********************************************************************************/
/* Problem: a568 "ISSC 2012- problem B" from ISSC 2012 */
/* Language: CPP (599 Bytes) */
/* Result: AC(217ms, 249KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-11-20 23:09:41 */
/**********************************************************************************/
#include <stdio.h>
int mypow(int x, int y, int mod) {
if(!y) return 1;
if(y&1)
return x*mypow(x*x%mod, y>>1, mod)%mod;
return mypow(x*x%mod, y>>1, mod);
}
int main() {
int n, m, tmp, i;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 1) printf("%d\n", 14%m);
else if(n == 2) printf("%d\n", 155%m);
else if(n == 3) printf("%d\n", 1575%m);
else {
tmp = 1575%m;
tmp = tmp*mypow(10, n-3, m)%m;
printf("%d\n", tmp);
}
}
return 0;
}
/*
14
155
1575
15750
157500
*/
暴搜幾筆之後找規律即可
14
155
1575
15750
157500
/**********************************************************************************/
/* Problem: a568 "ISSC 2012- problem B" from ISSC 2012 */
/* Language: CPP (599 Bytes) */
/* Result: AC(217ms, 249KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-11-20 23:09:41 */
/**********************************************************************************/
#include <stdio.h>
int mypow(int x, int y, int mod) {
if(!y) return 1;
if(y&1)
return x*mypow(x*x%mod, y>>1, mod)%mod;
return mypow(x*x%mod, y>>1, mod);
}
int main() {
int n, m, tmp, i;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 1) printf("%d\n", 14%m);
else if(n == 2) printf("%d\n", 155%m);
else if(n == 3) printf("%d\n", 1575%m);
else {
tmp = 1575%m;
tmp = tmp*mypow(10, n-3, m)%m;
printf("%d\n", tmp);
}
}
return 0;
}
/*
14
155
1575
15750
157500
*/