【Kuangbin数论】阿拉丁和飞毯

红太狼 2024-03-30 13:39 31阅读 0赞

[4577. 阿拉丁和飞毯 - AcWing题库][4577. _ - AcWing]

题意：

![ea349dd45bf947778b80c317e1c7f471.png][]

思路：

就是去求x和y

使得

1.x!=y

2.x\*y=a

3.min(x,y)=b

一开始想的是去根号n地枚举a的约数 ，然后直接统计

但是这样肯定T，所以换成dfs枚举约数去了

但是也T了

首先a\*a<=b的话直接特判成0，因为第三个条件

这道题我们要求约数个数，就不需要去枚举所有的约数

我们去分解质因数

ans不断地乘(质因子个数+1)就行

但是还有第三个条件需要满足

因此我们去去掉所有小于b的约数就行

因为前面特判过了，因此b一定是小于根号a的，保证了复杂度

时间复杂度为O(T\*根号a)

因为特判过了，所以这个复杂度不一定严谨

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    vector<pair<int,int> > v;
    int a,b,len=0,T=0,ta;
    int vis[mxn],prime[mxn];
    void init(int n){
    	for(int i=2;i<=n;i++){
    		if(!vis[i]) prime[++len]=i;
    		for(int j=1;prime[j]<=n/i;j++){
    			vis[i*prime[j]]=1;
    			if(i%prime[j]==0) break;
    		}
    	}
    }
    void solve(){
    	v.clear();len=0;
    	cin>>a>>b;
    	if(b*b>=a){
    		cout<<"Case "<<++T<<": "<<0<<'\n';
    		return;
    	}
    	ta=a;
    	for(int i=1;prime[i]<=a/prime[i];i++){
    		if(a%prime[i]==0){
    			int s=0;
    			while(a%prime[i]==0) a/=prime[i],s++;
    			v.push_back({prime[i],s});
    		}
    	}
    	if(a>1) v.push_back({a,1});
    	int ans=1;
    	for(int i=0;i<v.size();i++) ans*=(v[i].second+1);
    	ans/=2;
    	for(int i=1;i<b;i++){
    		if(ta%i==0) ans--;
    	}
    	cout<<"Case "<<++T<<": "<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	init(mxn);
    	while(__--)solve();return 0;
    }

总结：

1e12这种复杂度的去枚举约数肯定是要去dfs枚举

能特判的就先特判掉，降低复杂度

[4577. _ - AcWing]: https://www.acwing.com/problem/content/4580/
[ea349dd45bf947778b80c317e1c7f471.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4b5d0f04e36043f7af989bf6b890d399.png