EOJ Monthly 2019.5 (based on May Selection) B.幂运算

作者:神秘网友 发布时间:2020-09-09 06:42:35

EOJ Monthly 2019.5 (based on May Selection) B.幂运算

EOJ Monthly 2019.5 (based on May Selection) B.幂运算

EOJ Monthly 2019.5 (based on May Selection) B.幂运算
EOJ Monthly 2019.5 (based on May Selection) B.幂运算
这题是一道不容易写的数学题,并且题目只给了1s,就是说O(n)的算法都会T(我T了无数发),这时我们就要从别的方向考虑了。

我们发现a,b,c,d都是在1e9范围内的,就是说如果我们把a和c看成x ^ k1和x ^ k2,那么k1,k2<=32,这下子我们的运算量一下就小下来了。
题目要求的是a ^ b = c ^ d,我们把a,c按照上面那样处理,变成x ^ k1和x ^ k2,这样最后的式子就是x ^ (k1b)= x ^ (k2d)——>k1b = k2d。

最后答案由两部分组成:
平凡的情况:a=c,b=d 。
其他的情况:a≠c,就必须满足 k1 * b = k2 * d,为保证不重复计数,我们必须满足gcd(k1,k2)=1,然后我们跑两个(1,32)的 for 循环,再对每个满足条件的答案进行处理,这题也就不那么难了。

我这种做法的时间复杂度大概是O(32 * 32 * log n),但是好像别人有O(2 * 32 * log n)
的做法……

#include<bits/stdc++.h>
using namespace std;
#define maxn 300005
#define ll long long

const ll mod=1e9+7;
ll a,b,c,d;

ll poww(ll a,ll b){
    ll ans=1,base=a;
    while(b!=0){
        if(b&1!=0)ans=ans*base;
        base=base*base;
        b>>=1;
    }
    return ans;
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
		ll ans=b*d;
		for(int i=1;i<=32;i++)
			for(int j=1;j<=32;j++){
				if(__gcd(i,j)!=1)continue;
				ll A=pow(a,1.0/i);
				ll C=pow(c,1.0/j);
				while(poww(A,i)<=a)
					A++;
				while(poww(C,j)<=c)
					C++;
				A--;C--;
	            ans+=min(A-1,C-1)*min(b/j,d/i);
	            ans%=mod;
			}
		printf("%lld\n",ans);
	}
	return 0;
} 

EOJ Monthly 2019.5 (based on May Selection) B.幂运算相关教程

  1. echarts之基于geojson的自定义地图
  2. Django播放m3u8格式网络视频(videojs)
  3. 15日精读掌握《高德纳:具体数学》计划(2019.5/27-2019/6/10)
  4. 用shp制作geoJson格式地图数据(shp convert to geoJson)
  5. openlayer中geojson要素图层设置style样式
  6. shp平滑处理并转geojson
  7. 2019.5.25 提高A组 T2 JZOJ 4787 数格子
  8. Windows下idea破解教程2019.5.25(附激活码)