HDU 6814 Tetrahedron 分式取模

冷不防 2023-03-06 03:19 21阅读 0赞

[题目链接][Link 1]

Tetrahedron  
Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)  
Total Submission(s): 138 Accepted Submission(s): 57

Problem Description  
Generate three integers a, b, and c in \[1,n\] with equal probability independently, and use them as the three right-angle side length of a right-angled tetrahedron. Find the expectation of the reciprocal square of the distance from the right-angle apex to the slope (Euclidean distance).

For each test case, output a line containing the answer mod 998244353.

Input  
In the first line, you should read an integer T denoting the number of test cases.

In every test case, the only line will include an integer n.

It is guaranteed that T is no larger than 2×106 and n is no larger than 6×106.

Output  
For each test case, output the only line containing just one integer denoting the answer mod 998244353.

Sample Input  
3  
1  
2  
3

Sample Output  
3  
124780546  
194103070

Source  
2020 Multi-University Training Contest 5

#### 这本该是一道简单的数论题，我当时提交的时候这道题是过了的，我抱着试一试的心态，赛后交了一发，发现过不了，又交了一发别人的代码，发现也过不了，我觉得可能是————oj在忙，不想理你。 ####

##### 代码如下，如果你们之后提交我的代码，发现不能AK AC这道题的话，请在下方留言哈。 #####

#include <cstdio>
    
    using namespace std;
    typedef long long ll;
    const int max_n =6e6;
    const ll mod = 998244353;
    ll sum[max_n+1];
    
    void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d){
        
        if (!b) {
        d = a, x = 1, y = 0;}
        else{
        
            ex_gcd(b, a % b, y, x, d);
            y -= x * (a / b);
        }
    }
    
    ll inv(ll t, ll p){
        //如果不存在，返回-1
        ll d, x, y;
        ex_gcd(t, p, x, y, d);
        return d == 1 ? (x % p + p) % p : -1;
    }
    
    void init(){
        
    	ll ans=0;
    	for(ll i=1;i<=max_n;i++)
    	{
        
    		sum[i]=( sum[i-1] + inv(i*i%mod,mod) )%mod;
    	}
    }
    
    int main()
    {
        
    	init();保存取消管理置顶 编辑 删除0-
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
        
    		ll n;
    		scanf("%lld",&n);
    		ll ans=(3*sum[n]%mod) * inv(n,mod) %mod;
    		printf("%lld\n",ans);
    	}
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6814