求助!!用的字符串,TLE了两个 4 和 10,其他都AC
查看原帖
求助!!用的字符串,TLE了两个 4 和 10,其他都AC
984056
pppwolf楼主2023/6/7 13:25

求助!!用的字符串,TLE了两个 4 和 10,其他都AC

#include <iostream>
#include <cstring>
using namespace std;

void init_string(string &s1, string &s2)
{
  int len1 = s1.size();
  int len2 = s2.size();
  int num = abs(len1 - len2);
  if (len1 < len2)
  {
    while (num--)
    {
      s1 = '0' + s1;
    }
  }
  else if (len1 > len2)
  {
    while (num--)
    {
      s2 = '0' + s2;
    }
  }
}
// 高精度加法
string add(string s1, string s2)
{
  init_string(s1, s2);
  int op = 0; // 进位
  string ans = "";
  for (int i = s1.size() - 1; i >= 0; i--)
  {
    int temp = (s1[i] - '0') + (s2[i] - '0') + op;
    op = temp / 10;
    temp %= 10;
    ans = char(temp + '0') + ans;
  }
  if (op != 0)
    ans = char(op + '0') + ans;
  return ans;
}


// 高精度乘低精度
string mul_low(string s1, int x)
{
  int num = 0;
  string ans = "";
  while (x)
  {
    int temp = x % 10;
    int op = 0;
    string tempstr;
    for (int i = s1.size() - 1; i >= 0; i--)
    {
      int tem = (temp * (s1[i] - '0') + op) % 10;
      op = (temp * (s1[i] - '0') + op) / 10;
      tempstr = char(tem + '0') + tempstr;
    }
    if (op != 0)
      tempstr = char(op + '0') + tempstr;
    for (int i = 0; i < num; i++)
      tempstr += '0';
    ans = add(ans, tempstr);
    x /= 10;
    num++;
  }
  ans.erase(0, ans.find_first_not_of('0')); // 去除前导0
  if (ans.empty())
    ans = "0";
  return ans;
}

int main()
{
  int n;
  cin >> n;
  while (n--)
  {
    int a, b, ans = 0;
    string str = "1";
    cin >> a >> b;
    for (int i = 1; i <= a; i++)
    {
      str = mul_low(str, i);
    }
    for (int i = 0; i < str.size(); i++)
    {
      if (str[i] == char(b + '0'))
        ans++;
    }
    cout << ans << endl;
  }
  return 0;
}
2023/6/7 13:25
加载中...