【NOIP2016提高A组模拟9.15】Math

本文主要是介绍【NOIP2016提高A组模拟9.15】Math，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Sample Input

3 5

Sample Output

-1

Data Constraint

$n<10^7$
$m<10^{14}$

Solution

发现如果答案减一，那肯定是i*j是完全平方数
O(n)枚举i，O(1)求出i*j为完全平方数的个数就行了
线性求用线筛

#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define fo(i,a,b) for(ll i=a;i<=b;i++)
#define N 10000000 
using namespace std;
int p[N+1],a[N+1],b[N+1];
bool bz[N+1];
ll n,m;
int main()
{scanf("%lld %lld",&n,&m);int ans=0;bz[1]=1;a[1]=1;fo(i,2,n){if(!bz[i]) p[++p[0]]=i,a[i]=i,b[i]=1;ll j=i;fo(k,1,p[0]){ll o=p[k]*i;if(o<=N) bz[o]=1;else break;if(i%p[k]==0) {b[o]=1-b[i];if(b[o]==1) a[o]=a[i]*p[k];else a[o]=a[i]/p[k];break;}b[o]=1;a[o]=a[i]*p[k];}}fo(i,1,n){ll p=(int)(sqrt(m*1.0/a[i])+0.00000001);if(p%2==0) ans++;else ans--;}printf("%d",ans);
}

这篇关于【NOIP2016提高A组模拟9.15】Math的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---