^=^笑脸

admin管理员组

文章数量:1123061

^=^笑脸

^=^笑脸

题目描述

求有多少组a,b,c,d，满足a^b=c^d。（a,b,c,d均不超过N）
答案对(10^9 + 7)取模。

输入格式 2004.in

一共有T组测试数据。（不超过5）
共T行，一行一个整数N。

输出格式 2004.out

一共T行，一行一个整数，每组数据的方案数。

输入样例 2004.in

5
2
3
100
22306
1

输出样例 2004.out

6
15
21620
68467
1
【数据范围】
N不超过1000000。1^1=1^2，1^2=1^1算做不同的两组。

样例2解释：
1^1=1^1
1^1=1^2
1^1=1^3
1^2=1^1
1^2=1^2
1^2=1^3
1^3=1^1
1^3=1^2
1^3=1^3
2^1=2^1
2^2=2^2
2^3=2^3
3^1=3^1
3^2=3^2
3^3=3^3

    在考试的时候，这题一直想着用勾股数那样的方法，公式变形一下，然后去掉几个for循环，但是发现不管怎么样，平方数都是很大的，而且也好像没有什么可以变形的东西。

    题解是yhf大佬想出来的，强。

思路分析：

    首先，我们会知道，两个数的平方是可以化作同样的x^y。这句话怎么理解呢？举个例子：16^4=4^8。观察16，也可以化成4^2，因此，16^4==（4^2）^4=4^8。

    所以，只要枚举一个相同的底数x就可以了，就比如上面的例子，相同的底数是4。我们可以把一个数看做是(x^a)^b=(x^c)^d。然后枚举得出a和c，a和c是不会太大的，因为x^a不能大于n，是指数级别的。

    现在的问题是，对于已知的(x^a)和(x^c)，存在多少对（b,d），能使得(x^a)^b=(x^c)^d。

    看作x^(ab)和x^(cd)，与上面的(x^a)^b=(x^c)^d是等价的。而使得ab=cd，最小的ab=cd显然是它们的最小公倍数lcm。

    而b和d最多可以是n，那么an与bn则是最大的，用an/lcm与bn/lcm，便可以得出有多少对了，当然要再两者之中取一个min，至于公示上的理论，可以参考以下这篇博文：

关于辗转相除法：

    说来惭愧，本来是很入门级别的辗转相除法我已经忘记了，还是借助度娘才编了出来，这是一个很有用的东西，用来求最大公因数。

long long gcd(long long a,long long b)
{long long c=a%b;while(c!=0){a=b;b=c;	c=a%b;}return b;
}//求最大公因数 

    而得出最大公因数以后便可以得出最小公倍数，用短除法的道理推以下就可以知道了。 最小公倍数lcm=a*b/gcd。

细节：

    因为我们一开始枚举的底数x一定是划到最简的数字（没有哪个数的平方可以组成），可以用一种类似于筛素数的方法把一些不符合条件的筛出来。

#include#includeusing namespace std;
const int mod=1000000007,maxn=1000005;
int t,v[maxn];
long long n,ans;long long gcd(long long a,long long b)
{long long c=a%b;while(c!=0){a=b;b=c;	c=a%b;}return b;
}//求最大公因数 void zhi()
{for(int i=2;i<=maxn;i++){long long k=i;for(int j=1; ;j++){k=k*i;if(k>maxn) break;else v[k]=1;}}
}void caozuo()
{for(int x=2;x<=n;x++){if(v[x]==1) continue;for(long long a=1,now=x;now<=n;a++,now*=x){for(long long c=1,now2=x;now2<=n;c++,now2*=x){int f=gcd(a,c);//最小公因数 long long lcm= a*c%mod/f;int num=a*n/lcm%mod; int num2=c*n/lcm%mod; ans=( ans+ min(num,num2) )%mod;}}}
}int main()
{freopen("2004.in","r",stdin);freopen("2004.out","w",stdout);cin>>t;zhi();while(t){t--;ans=0;cin>>n;ans=(n*n)%mod;caozuo();cout<<

本文标签： 笑脸