qboimathtest1 t1 魔法串

题目

小 N 最近在沉迷数学问题。

对于一个数字串 S，如果可以将它划分成两个数字 A、B，满足：

1、 S=AB。

2、 A、B 均不包含前导 0。

3、 B 是 A 的倍数，且B / A是完全立方数。

那么小 N 就认为该划分是一个“好划分”。如对于数字串“11297”，（11， 297）就是一个“好划分”。

如果一个数字串 S 至少有两个“好划分”，那么小 N 就认为 S 是一个“魔法串”。如数字串“1335702375”就是一个“魔法串”，其“好划分”有（1， 335702375）和（133，5702375）。

现在给定正整数 N，小 N 需要你帮她求出一个长度恰好为 N 的“魔法串”S，如果无解请输出“QwQ”（不带引号）。

【输入】

一行一个正整数 N。

【输出】

一行一个长度恰好为 N 的“魔法串”S，如果无解请输出“QwQ”（不带引号）。

【输入输出样例】

【输出样例】

1124784124392112128

【数据范围】

对于 30%的数据： 1 ≤ N ≤ 10。

对于 50%的数据： 1 ≤ N ≤ 35。

对于 100%的数据： 1 ≤ N ≤ 100。

分析

当N <= 4时无解。

如果数字串S是一个魔法串，那么向 S 后面添加 “000” 后得到的新串也是一个魔法串。那所以只需要求出N = 5、6、7时的可行解，就可以推广到所有情况。这样的可行解之一是73584(000)*、324000(000)*、1621296(000)*。时间复杂度：O(N）

搜索或手玩并打表，可以拿到30 ~ 50分。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

int main(){

    int n;

    cin>>n;

    if(n<=)puts("QwQ");

      else {

          if(n%==){

              n-=;

              cout<<;

              for(int i=;i<=n;i++)cout<<;

          }else if(n%==){

              n-=;

              cout<<;

              for(int i=;i<=n;i++)cout<<;

          }else {

              n-=;

              cout<<;

              for(int i=;i<=n;i++)cout<<;

          }

      }

    return ;

}

巴特西

qboimathtest1 t1 魔法串

最新文章

热门文章