steve 学完了快速幂, 现在会他快速的计算:(ij)%d , Alex 作为一个数学大师, 给了 steve 一个问题: 已知
i∈[1,n],j∈[1,m] , 计算满足 (ij)%d=0 的 (i,j) 的对数.
输入格式
T 组输入, 对于每一组输入三个数 n,m,d.
(1≤T≤1000,1≤n,m,d≤109).
输出格式
对于每组输入, 输出答案, 每个答案占一行.
样例
- input
- 4
- 3 10 7
- 3 5 3
- 10 30 6
- 100 100 8
- output
- 0
- 5
- 30
- 4937
不太懂,, 先记下来再说
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll qpow(ll a,ll b){
- ll ans=1;
- while(b){
- if(b&1) ans=(ans*a);
- a=(a*a);
- b>>=1;
- }
- return ans;
- }
- int main(){
- int T;scanf("%d",&T);
- while(T--){
- ll n,m,d;
- scanf("%lld %lld %lld",&n,&m,&d);
- vector<pair<ll,ll>> prs;
- vector<pair<ll,ll>>::iterator it;
- for(ll i=2;i*i<=d;i++){
- if(d%i==0){
- long long cnt=0;
- while(d%i==0){
- d/=i;cnt++;
- }
- prs.push_back({i,cnt});
- }
- }
- ll res=0;
- if(d!=1) prs.push_back({d,1});
- for(ll j=1;j<=min(m,1LL*30);j++){
- ll g=1;
- // for(auto v:prs)
- for(it=prs.begin();it!=prs.end();it++)
- {
- g*=qpow( it->first,( it->second+j-1)/j);
- }
- if(j==30) res+=(m-29)*(n/g);
- else res+=n/g;
- }
- printf("%lld\n",res);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3161294.html