bc19&&hdoj5108&&hdoj5109 Alexandra and Prime Numbers Alexandra and A*B Problem

92 阅读 0 评论 61 点赞

我是靠谱客的博主纯情板栗，最近开发中收集的这篇文章主要介绍bc19&&hdoj5108&&hdoj5109 Alexandra and Prime Numbers Alexandra and A*B Problem，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Alexandra and Prime Numbers

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1632 Accepted Submission(s): 557

Problem Description

Alexandra has a little brother. He is new to programming. One day he is solving the following problem: Given an positive integer N, judge whether N is prime.
The problem above is quite easy, so Alexandra gave him a new task: Given a positive integer N, find the minimal positive integer M, such that N/M is prime. If such M doesn't exist, output 0.
Help him!

Input

There are multiple test cases (no more than 1,000). Each case contains only one positive integer N.

N≤1,000,000,000 .
Number of cases with

N>1,000,000 is no more than 100.

Output

For each case, output the requested M, or output 0 if no solution exists.

Sample Input

Sample Output

Source

BestCoder Round #19

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<vector>
#define inf 0x3f3f3f3f
using namespace std;
bool prime(long long n){
if(n==1)return false;
for(long long i=2;i*i<=n;++i){
if(n%i==0)return false;
}
return true;
}
int main()
{
long long n,i;
while(scanf("%lld",&n)!=EOF){
long long ans=inf;
bool sign=false;
for(i=1;i*i<=n;++i){
if(n%i==0){
if(prime(i)){
sign=true;
ans=min(ans,n/i);
}
if(prime(n/i)){
sign=true;
ans=min(ans,i);
}
}
}
if(sign)
printf("%lldn",ans);
else
printf("0n");
}
return 0;
}

Alexandra and A*B Problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 777 Accepted Submission(s): 199

Problem Description

Alexandra has a little brother. He is new to programming. One day he is solving the following problem: Given two positive integers A and B, output A*B.
This problem is even easier than the last one. Alexandra can't wait to give him another task: Given a positive integer A and a string S(S only contains numbers.), find the minimum positive integer B, such that S is a substring of T, where T is the decimal notation of A*B.
See the sample for better understanding.
Note: S can contain leading zeros, but T can't.

Input

There are multiple test cases (no more than 500). Each case contains a positive integer A and a string S.

A≤10,000,1≤|S|≤8 .

Output

For each case, output the required B. It is guaranteed that such B always exists.
To C++ programmers: if you want to output 64-bit integers, please use "%I64d" specifier or cout.

Sample Input

Sample Output

Source

BestCoder Round #19

最后的A*B应该是xSy的形式，其中y可以为空，并且如果S不以0开头那么x也可以为空。首先枚举y的长度。在y的长度确定之后，显然x应该越小越好。所以从小到大枚举x。设S的长度为p，y的长度为q，那么可以列方程：

x*10^p + S)*10^q + y) mod A = 0

。解出y以后，如果

y<10^q

那么解合法。容易证明，我们只需从0（或1，如果S以0开头）到A枚举x，那么所有的解一定会被枚举到。对于q=0的情况，x的长度不会超过4(因为A<=10000)，所以y的长度也只需要枚举到4就可以了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<vector>
#define inf 0x7ffffff
using namespace std;
char bit[10];
long long Pow[20];
void init(){
Pow[0]=1;
for(int i=1;i<=18;++i){
Pow[i]=Pow[i-1]*10;
}
}
int main()
{
init();
int i,j,k;
long long n,ans,pre;
while(scanf("%lld%s",&n,bit)!=EOF){
int len=strlen(bit);ans=1e18;
long long num;sscanf(bit,"%lld",&num);
for(i=0;i<5;++i){//枚举y的长度
for(pre=0;pre<=Pow[4-i];++pre){//枚举x
if(bit[0]=='0'&&pre==0)continue;
if(bit[0]!='0'&&pre==Pow[4-i])continue;
long long cnt=pre*Pow[len+i]+num*Pow[i];
long long l=(n-cnt%n)%n;
if(l<Pow[i])ans=min(ans,cnt+l);
}
}
printf("%lldn",ans/n);
}
return 0;
}