牛牛和羊羊在玩一个有趣的猜数游戏。在这个游戏中,牛牛玩家选择一个正整数,羊羊根据已给的提示猜这个数字。第i个提示是"Y"或者"N",表示牛牛选择的数是否是i的倍数。
例如,如果提示是"YYNYY",它表示这个数使1,2,4,5的倍数,但不是3的倍数。
注意到一些提示会出现错误。例如: 提示"NYYY"是错误的,因为所有的整数都是1的倍数,所以起始元素肯定不会是"N"。此外,例如"YNNY"的提示也是错误的,因为结果不可能是4的倍数但不是2的倍数。
现在给出一个整数n,表示已给的提示的长度。请计算出长度为n的合法的提示的个数。
例如 n = 5:
合法的提示有:
YNNNN YNNNY YNYNN YNYNY YYNNN YYNNY
YYNYN YYNYY YYYNN YYYNY YYYYN YYYYY
所以输出12
[编程题]猜数游戏
思路： 1.第i个数是素数，那么dp[i]=dp[i-1]*2，这是因为素数和前面的所有数都没有依赖关系，因此YN都行 2.第i个数不是素数的幂次，也就是像6这样的数字，你会发现，它已经被2,3唯一确定了，例如23分别是YY，那么6一定是Y，23分别是YN或NY或NN，6一定是N，所以说这时候有dp[i]=dp[i-1]
3.第i个数是素数的幂次，它不能唯一确定，比如4，当2为Y时，4不确定，可以是Y，也可以是N。将4和2放入集合，若2取，4必定取，所以有NN，YN，YY三种情况。那么引申一下，加入8就是3个元素的集合，共4种情况，9就是2个元素的集合（3、9），有3种情况，以此类推。最后将这些情况相乘即可，因为这些集合之间相互不影响
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
using namespace std;
const int MOD = 1E9+7;
const int maxn = 1e6+5;
int vis[maxn];
int main()
{
int n;
while(cin >> n)
{
long long ans = 1;
for(int i = 2; i <= n; i++)
{
int cnt = 0;
if(vis[i])
continue;
for(int j = i+i; j <= n; j += i) //处理他的倍数
{
vis[j] = 1;
}
//求i的幂次
long long mi = i; //用 int 会溢出
while(mi <= n)
{
cnt++;
mi *= i;
}
ans = ans * (cnt + 1) % MOD;
}
cout << ans << endl;
}
}
发表于 2017-07-26 14:50:33
回复(15)
思路：设dp[i]表示输入长度为i时的合法的提示个数，那么根据i的分类可能存在下面几种情况：
- i为素数，由于素数和前面的所有数都没有依赖关系，即第i位可以为Y或者N，所以dp[i]=dp[i-1]*2；
- i不是素数的幂次，也就是像6这样的数字，你会发现，它已经被第2位和第3位唯一确定了。例如23分别是YY，那么6一定是Y；23分别是YN或NY或NN，6一定是N，所以说这时候有dp[i]=dp[i-1]
- i是素数的幂次，它不能唯一确定。例如4，当2为Y时，4不确定，可以是Y，也可以是N。将4和2放入集合，若2取，4必定取，所以有NN，YN，YY三种情况。那么引申一下，加入8就是3个元素的集合，共4种情况，9就是2个元素的集合（3、9），有3种情况，以此类推。最后将这些情况相乘即可，因为这些集合之间相互不影响
因此，从上面分析中可以看出，长度为n的各位可以分为两类：
- 位数为素数或素数的幂次：这些位上的可能性取决于素数的幂次且小于n的那些数。
- 位数不是素数且不是素数的幂次：当素数位的字符确定了，这些位上的字符也都确定，即都只有一种可能性；
举个例子，当n=16，存在素数2，3，5，7，11，13。
素数2，2的幂次数有2，4，8，16。从后往前看，依次看16，8，4，2的字符取值。如果16取值为Y，那么2，4，8都只能为Y;如果16为N，则此时需要看8，如果8取值为Y，那么2，4都只能为Y；如果8为N，那么此时需要看4，如果4为Y，则此时2为Y；如果4为N，那么此时需要看2，2存在两种情况，结束。总的可能性为5种，为2的幂次数的个数+1。
素数3，3的幂次数有3，9。同样的，先看9，如果9取值为Y，则3为Y；如果9取值为N，那么此时看3，3存在两种可能性，结束。总的可能性为3，为3的幂次数的个数+1。
素数5，7，11，13，他们的幂次数都各只有一个，都为2，是各自素数的幂次数的个数+1。
所以，合法提示组合数问题转化为求所有小于等于n的素数及他们的幂次数的组合数的乘积。也就是把每一个素数和它的幂次归为一类，求出每一类的合法提示组合数，由于类与类之间没有重叠关系，因此总的组合数为所有类的组合数的乘积。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int len=scanner.nextInt();
long ans=1;
boolean[] visited = new boolean[len+1];
for(int i=2; i<=len; i++) {
if(visited[i])
continue;
for(int j=2*i; j<=len; j+=i)
visited[j] = true;
int count=0;
long k=i; //int会溢出
while(k<=len) {
k*=i;
count++;
}
ans=ans*(count+1)%1000000007;
}
System.out.println(ans);
}
}
编辑于 2017-08-03 10:10:06
回复(6)
<div> 各位大牛没时间回答，我长时间看(抄)各位大手子的代码，来简单说下思路。一开始以为是dp呢，设dp[i]代表输入长度为i时的答案，就开始找递推关系了，分几种情况： </div> <div> 1.第i个数是素数，那么dp[i]=dp[i-1]*2，这是因为素数和前面的所有数都没有依赖关系，因此YN都行 </div> <div> 2.第i个数不是素数的幂次，也就是像6这样的数字，你会发现，它已经被2,3唯一确定了，例如23分别是YY，那么6一定是Y，23分别是YN或NY或NN，6一定是N，所以说这时候有dp[i]=dp[i-1] </div> <div> 3.第i个数是素数的幂次，这种情况很难受，它不能唯一确定，比如4，当2为Y时，4不一定为什么，可以是Y，也可以是N，这就很难受了，这意味着我们要求dp[4]还得记录dp[3]时2的位置的情况，这没法做。。因此dp的方法我就不会了，然后在群里看到了某个大牛的代码，又思考了一下，原来4可以看成由2个2唯一表示，2个2总共有3中情况（YY,YN,NN），其中NY不行，因为这几个2其实是有顺序的，第一个2是2，第二个2其实是4，因此4可以看成是2个2组成的序列，而且这个序列总共的情况是3种，和3这个位置互相没有影响，因此做乘法运算就能得到正确结果。那么引申一下，8就是3个2组成的序列，共4种情况，9就是2个3组成的序列，有3种情况，以此类推。 </div> <div> <br> </div> <div> 明白了以上几点，这个问题就变成了找n以内的素数以及n以内的素数的幂次，用10来举例吧，1我们不考虑，2是素数，它的10以内幂次是2,4,8，因此有4种情况。接下来是3，它10以内的幂次是3,9，因此有3种情况，4我们考虑完了，5有2种情况，6由2和3唯一确定不需要考虑，7有2种情况（Y和N），8我们也考虑完了，9我们也考虑完了，10 由2和5唯一确定，因此总共的情况就是素数序列的个数乘积即num(2)*num(3)*num(5)*num(7)（4*3*2*2=48） </div> <div> <br> </div> <div> 欢迎批评指正，大家一起学习进步，找到心仪的工作，<span>实现自己的梦想，</span><span>2017加油！</span> </div> <div> ps:最后说一句题外话，希望LPL在S7取得好成绩！！(我不是猪崽，不过厂长努力拼搏的精神还是非常值得学习的！)（逃。。。 </div>
编辑于 2017-07-26 18:14:23
回复(9)
#include<stdio.h>
#include<string.h>
int isp[1000005];
const int mod=1000000007;
int main(){
int N,i,j;
while(scanf("%d",&N)!=EOF){
memset(isp,0,sizeof(isp));
long long ans=1;
for(i=2;i<=N;i++){
if(!isp[i]){
for(j=2*i;j<=N;j+=i)
isp[j]=1;
}else continue;
long long tmp=i,cnt=0;
while(tmp<=N){
tmp*=i;
cnt++;
}
//printf("i:%d cnt:%d\n",i,cnt);
ans=ans*(cnt+1)%mod;
}
printf("%lld\n",ans);
}
}//找规律....
//例子 n=16 2的4次幂在16之内 3的2次幂在16之内 5的1次幂在16之内
// 7的1次幂在16之内 11的1次幂在16之内 13的1次幂在16之内
//接下来 把 (幂+1) 相乘 即:(4+1)*(2+1)*(1+1)*(1+1)*(1+1)*(1+1)=5*3*2*2*2*2=240
//流程就是 把素数的幂找一遍 +1 相乘
发表于 2017-08-02 19:20:28
回复(1)
#include<iostream>
#include<vector>
//#include<string>
//#include <algorithm>
#include<cmath>
using namespace std;
bool IsPrimer(int n)
{
if (n<2)
{
return false;
}
for (int i = 2; i <=sqrt(n); i++)
{
if (n!=2&&n%i==0)
{
return false;
}
}
return true;
}
int main()
{
int n;
while (cin>>n)
{
vector<int> ivec;
int ans = 1;
for (int i = 2; i <= n; i++)
{
if (IsPrimer(i))////找素数
{
for (int j = 1; j <= n; j++)
{
if (pow(i, j) > n)//素数幂次个数
{
ivec.push_back(j);
break;
}
}
}
}
for (size_t i = 0; i < ivec.size(); i++)
{
ans = ans*ivec[i] % 1000000007;
}
cout << ans << endl;
}
return 0;
}
发表于 2017-07-27 22:31:37
回复(0)
这道题比较难。
首先运用动态规划的思想
首先我们分析，dp[i]表示前i个数的合法个数
当第i个数是素数的时候，前面除了1都没有能除尽的，所以这个位置可以随便选Y或N,所以dp[i] = dp[i-1]
当第i个数不是素数的幂次，比如6，10这种数，那么他们的情况实际上是被前面的数所决定的，对6来说，如果2，3为YY,那么6必然是Y，其他情况6必须是N,所以dp[i] = dp[i-1]
当第i个数是素数的幂次的时候，也就是2，4，8，16这种数，这时候情况就复杂了。假设现在有2，4，8，那么有多少种情况呢，我们仔细分析也能找出规律
YYY,YNN,NNN，YYN就这四种情况
对于2，4
YN,YY,NN三种情况
我们发现实际上也是有规律的，首先都能或者都不能两种，然后就是从左到右添加Y：
YNN,YYN。
所以对于这种情况，我们得出规律，如果有n个幂次，就有n+1中可行的情况。
分析完之后，我们就可以得出计算方法，对于12：
2，4，8这三个数是幂次，有4中可能
3，9 这两个数幂次，有三种可能
5，7，11，分别是两种可能
其他的数都由其他数决定
所以最后结果就是43222
所以我们思考一下，最后就变成了找素数和素数幂次的个数了。
代码
import java.util.*; public class Main { final static int MAX = (int) (1e6+5); final static int MOD = (int) (1E9+7); static boolean[] visited = new boolean[MAX]; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); in.close(); System.out.println(helper(n)); } private static long helper(int n) { long ans = 1; for(int i=2;i<=n;i++) { int count = 0; if(visited[i]) continue; for(int j=i+i;j<=n;j+=i) { visited[j] = true; } long mi = i; while(mi <= n) { count++; mi = mi*i; } ans = ans * (count+1) % MOD; } return ans; } }
发表于 2017-07-27 18:26:44
回复(1)
count=1;
对于i从2至n，如果i为素数那么count=count*（k+1），其中k是使得ik<=n的最大k值。
#include <iostream>
#include <vector>using namespace std;
int main(){
int n;
cin>>n;
vector<int> sushu(n+1,1);
int count=1;
for(int i=2;i<n+1;i++){
if(sushu[i]==1){
long long tmp=1;
int k=count;
for(;tmp*i<n+1;){
tmp=tmp*i;
k=(k+count)%1000000007;
}
count=k;
for(int j=2;j*i<n+1;j++){//求解素数
sushu[j*i]=0;
}
}
}
cout<<count<<endl;
return 0;
}
编辑于 2017-08-27 14:09:07
回复(0)
分享一个思路，如果输出排成一个数列A，那么可以看出规律
可分4种情况：(n为数列下标)
1.n=1
2.n为质数
3.n为素数的幂次
4.n为其他情况
4种情况对应规律：
1.A(1)=1
2.A(n)=2*A(n-1)
3.A(n)=A(n-1)*(j+1)/j // 其中 i的j次方等于n,i为质数 例如8是2的3次方，所以n=8时，A(8)=A(7)*4/3
4.A(n)=A(n-1)
有一个缺点是这样写代码可能会使算法复杂度增大,我试着写了下，很可惜运行超时
======================================================================
import java .util.Scanner;
public class Main{
public static void main(String [] args){
int count=1;
Scanner input=new Scanner(System.in);
int n=input.nextInt();
for(int i=2;i<=n;i++){
if(n==1){
count=count;
}else if(isPrime(i)){
count=2*count;
}else if(Method(i)>1){
count=(int) (count*Method(i));
}else{
count=count;
}
}
System.out.println(count);
}
//当n为质数的幂次的情况
public static double Method(int N){
for(double i=2;i<N;i++){
for(double j=2;j<=N;j++){
if(Math.pow(i,j)==N){
return (j+1)/j;
}
}
}
return 0;
}
//判断n为质数的情况
public static boolean isPrime(int N){
boolean flag=true;
if(N<2){
return false;
}else{
for(int i=2;i<N;i++){
if(N%i==0){
flag=false;
break;
}
}
}
return flag;
}
}
======================================================================
如果思路有错或者代码有可以优化的地方，还请大佬指点指点。
编辑于 2017-08-13 21:23:49
回复(0)
看来最后一道题真的不简单，提交三次才做出正确答案。第一次思路不对就如@EDG_Clearlove7同学说的那样，素数幂次的情况考虑不周，第二次思路正确但是查找素数的算法过于繁琐超时了。把超时和正确的代码都贴上供大家参考吧。
1.超时方案：
importsysdef primenum(n): from math importsqrt ifn%2== 0: returnn==2 ifn%3== 0: returnn==3 ifn%5== 0: returnn==5 forp in xrange(7,int(sqrt(n)+1),2): ifn%p == 0: return0 return1 def maxn(x,y): res=x;n=0 whileres<=y: n += 1 res*=x returnn if__name__ == "__main__": n = int(sys.stdin.readline().strip()) #n+=2 max_n = 1 fori in xrange(2,n+1): ifprimenum(i): l=maxn(i,n) max_n *= (l+1) print max_n % 1000000007
********************************************************
2.正确方案：
importsys
def prime(n):
flag = [1]*(n+2)
p=2
res=[]
while(p<=n):
res.append(p)
fori in range(2*p,n+1,p):
flag[i] = 0
while1:
p += 1
if(flag[p]==1):
break
returnres[:]
def maxn(x,y):
res=x;n=0
whileres<=y:
n += 1
res*=x
returnn
if__name__ == "__main__":
n = int(sys.stdin.readline().strip())
#n+=2
max_n = 1
a=[];a.extend(prime(n))
fori in a:
l=maxn(i,n)
max_n *= (l+1)
print max_n % 1000000007
发表于 2017-07-31 11:40:25
回复(3)
谢谢楼上大佬的分享。
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
bool isPrime(int a){
for(int i=2;i<=sqrt(a);i++){
if(a!=2 && a%i==0){
return false;
}
}
return true;
}
int main(){
int n;
cin>>n;
vector<int> res;
long long ans=1;
int count=0;
for(int i=2;i<n+1;i++){
if(isPrime(i)){
for(int j=1;j<n;j++){
if(pow(i,j)<=n)
{
count++;
}
else{
break;
}
}
res.push_back(count+1);
count=0;
}
}
for(int i=0;i<res.size();i++){
ans=ans*res[i]%1000000007;
}
cout<<ans<<endl;
return 0;
}
发表于 2017-07-27 17:18:04
回复(0)
链接：https://www.nowcoder.com/questionTerminal/0a5b316cfe9d4c4ba89c6c57a1ee516e
来源：牛客网
任意一个正整数字都是由某几个素数的多少次幂相乘得到，比如任意数字m（m只是该题中小于等于n里面的一个数字而已）可以由素数a，素数b，素数c求得，那么数字m=
*
*
（x,y,z可以等于零至无穷）那么只需要将小于n里面的所有素数的所有幂次项确定即可。
来源：牛客网
任意一个正整数字都是由某几个素数的多少次幂相乘得到，比如任意数字m（m只是该题中小于等于n里面的一个数字而已）可以由素数a，素数b，素数c求得，那么数字m=
发表于 2020-08-19 20:18:41
回复(0)
又又又又又不对 想了俩小时 自己的电脑结果是对的 结果到这里又又又堆栈溢出了 求解答啊啊啊啊啊
#include<iostream>
using namespace std;
#define Maxsize 1000
int chushu;
int TypeOfNum( int n )
{
int i;
int num = 0;
for(int j = 2; j <= n / 2; j++)
{
int m = n;
while(m % j == 0 && m / j >= 1)
{
m = m / j;
num++;
if( m == 1)
{
chushu = j;
return num;
}
}
}
for( i = 2; i <= n / 2; i++)
if( n % i == 0)
return 1;
return 0;
}
int main(){
long int n;
long int count[Maxsize];
int num = 0;
cin>>n;
count[1] = 1;
for(int i = 2; i <= n; i++)
{
if(TypeOfNum(i) == 0)
count[i] = 2 * count[i - 1];
else if(TypeOfNum(i) == 1)
count[i] = count[i - 1];
else
count[i] = (TypeOfNum(i) + 1) * count[i - 1] / TypeOfNum(i);
}
cout<<count[n];
return 0;
}
发表于 2017-08-24 18:34:22
回复(0)
注意数据溢出的情况，两个int类型相乘就有可能溢出
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
vector<bool> vis(n+1, false);
long long sum = 1;
for (long long i = 2; i <= n; i++)
{
if (vis[i])
continue;
int count = 1;
for (long long j = i*i; j <= n; j = j*i)
count++;
sum = sum*(count + 1) % 1000000007;
for (long long j = i + i; j <= n; j += i)
vis[j] = 1;
}
cout << sum << endl;
}
return 0;
}
编辑于 2017-07-31 11:46:58
回复(4)
根据高票大神的观点，写出如下的代码，但是，始终有四个数据的结果不对，最终发现，尽然是第三个for循环中，int型溢出导致，改成long型之后就可以正常AC了，汗。。。。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
int n = sc.nextInt();
System.out.println(solve(n));
}
}
private static long solve(int n) {
boolean[] include = new boolean[n+1];
long p = 1;
for (int i = 2; i <= n; i++) {
if(!include[i]) {
int count = 1;
for (int j = i; j <= n; j += i) {
include[j] = true;
}
for (long j = i; j <= n; j *= i) {
count ++;
}
p = (p * count) % 1000000007;
}
}
return p;
}
}
编辑于 2017-07-26 17:17:28
回复(2)
问题信息
通过挑战的用户
-
2023-09-03 17:09:03
-
2021-08-01 19:17:15
-
2021-07-19 09:14:25
-
2021-07-06 12:54:49 -
2021-07-02 19:18:35
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
