贝壳找房算数（中等）

题目链接：点击打开链接

描述

贝壳找房力求为每位用户找到满意的房子，最近贝壳找房通过大数据得出下面的一个结论，
求满足0<i,j<=n,f(i) * f(j)>0,且0 < gcd(f(i),f(j)) <= k的数对 (i,j)的数量，其中满足条件的对数就是可以满足某位用户的房源数目。
其中 f(x)表示 x 所有数位的积，比如 f(124)=1 * 2 * 4 = 8.
因答案很大，请求出其在模 998244353意义下的结果。其中 gcd(x, y)表示x和y的最大公约数。
提示： 其中 (1,2), (2,1)算是两种情况。

输入格式

一行两个正整数，分别表示 n和k。
保证1<=n<=1e6,1<=k<=1e18。

输出格式

一个整数表示答案。

样例输入

9 5

样例输出

77

思路

对于数位积相同的可以只算一次，用map存起来个数，这样就可以将复杂度压下来了。

代码

#include<bits/stdc++.h>
#pragma warning(disable:4786)
#define ll long long 
using namespace std;  inline ll hh(ll i){  //求数位积ll temp=1ll;  while(i){temp*=(i%10);  i/=10;  }return temp;
} 
int main(){//freopen("2.txt", "r", stdin);  ll n, k;  scanf("%lld%lld", &n, &k);  ll ans =0;  map<ll,ll>mp;  map<ll,ll>::iterator it1,it2;  for(ll i=1;i<=n;i++){  //一个个的求出数位积，放到map里ll temp=hh(i);  if(temp!=0)mp[temp]++;  }for(it1=mp.begin();it1!=mp.end();it1++){  //对于数位积，来个二重循环计算for(it2=it1;it2!=mp.end();it2++){if(__gcd((*it1).first,(*it2).first)<=k){  //通过algorithm里面的__gcd直接求公约数ll temp=(*it1).second * (*it2).second ;  ans +=temp;  ans %= 998244353;if(it1 != it2)ans +=temp;  //不是一样的，算两次ans %= 998244353;}}}printf("%lld\n",ans);  
}

贝壳找房算数（中等）

题目链接：点击打开链接

描述

贝壳找房力求为每位用户找到满意的房子，最近贝壳找房通过大数据得出下面的一个结论，
求满足0<i,j<=n,f(i) * f(j)>0,且0 < gcd(f(i),f(j)) <= k的数对 (i,j)的数量，其中满足条件的对数就是可以满足某位用户的房源数目。
其中 f(x)表示 x 所有数位的积，比如 f(124)=1 * 2 * 4 = 8.
因答案很大，请求出其在模 998244353意义下的结果。其中 gcd(x, y)表示x和y的最大公约数。
提示： 其中 (1,2), (2,1)算是两种情况。

输入格式

一行两个正整数，分别表示 n和k。
保证1<=n<=1e6,1<=k<=1e18。

输出格式

一个整数表示答案。

样例输入

9 5

样例输出

77

思路

对于数位积相同的可以只算一次，用map存起来个数，这样就可以将复杂度压下来了。

代码

#include<bits/stdc++.h>
#pragma warning(disable:4786)
#define ll long long 
using namespace std;  inline ll hh(ll i){  //求数位积ll temp=1ll;  while(i){temp*=(i%10);  i/=10;  }return temp;
} 
int main(){//freopen("2.txt", "r", stdin);  ll n, k;  scanf("%lld%lld", &n, &k);  ll ans =0;  map<ll,ll>mp;  map<ll,ll>::iterator it1,it2;  for(ll i=1;i<=n;i++){  //一个个的求出数位积，放到map里ll temp=hh(i);  if(temp!=0)mp[temp]++;  }for(it1=mp.begin();it1!=mp.end();it1++){  //对于数位积，来个二重循环计算for(it2=it1;it2!=mp.end();it2++){if(__gcd((*it1).first,(*it2).first)<=k){  //通过algorithm里面的__gcd直接求公约数ll temp=(*it1).second * (*it2).second ;  ans +=temp;  ans %= 998244353;if(it1 != it2)ans +=temp;  //不是一样的，算两次ans %= 998244353;}}}printf("%lld\n",ans);  
}