Problem I. Count

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

Total Submission(s): 42 Accepted Submission(s): 16

Problem Description

Multiple query, for each n, you need to get

n i-1

∑ ∑ [gcd(i + j, i - j) = 1]

i=1 j=1

Input

On the first line, there is a positive integer T, which describe the number of queries. Next there are T lines, each line give a positive integer n, as mentioned above.

T<=1e5, n<=2e7

Output

Your output should include T lines, for each line, output the answer for the corre- sponding n.

Sample Input

4 978 438 233 666

Sample Output

194041 38951 11065 89963

Source

Recommend

chendu | We have carefully selected several similar problems for you:

题意：求下面这个式子的值

n i-1

∑ ∑ [gcd(i + j, i - j) = 1]

i=1 j=1

分析：按照上面那个式子直接暴力打表容易得到上面式子的含义是1-n以内偶数的欧拉函数值加上奇数的欧拉函数值除以2的和（注意要快速打表，运用素数快速打表）

AC代码：

#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #define ls (r<<1)#define rs (r<<1|1)#define debug(a) cout << #a << " " << a << endlusing namespace std;typedef long long ll;const ll maxn = 2*1e7+10;const ll mod = 998244353;const double pi = acos(-1.0);const double eps = 1e-8;ll num[maxn], sum[maxn], prim[maxn];int main() { ios::sync_with_stdio(0); ll T, n; memset(num, 0, sizeof num); num[1] = 1; ll id = 0; for( ll i = 2; i <= maxn-10; i ++ ) { if(!num[i]) { num[i] = i - 1; prim[id++] = i; } for( ll j = 0; j < id && prim[j]*i <= maxn-10; j ++ ) { if(i % prim[j]) { num[i*prim[j]] = num[i] * (prim[j]-1); } else { num[i*prim[j]] = num[i] * prim[j]; break; } } } num[1] = 0; sum[1] = 0; for( ll i = 2; i <= maxn-10; i ++ ) { if( i%2 == 0 ) { sum[i] = sum[i-1] + num[i]; } else { sum[i] = sum[i-1] + num[i]/2; } } scanf("%lld",&T); while( T -- ) { scanf("%lld",&n); printf("%lld\n",sum[n]); } return 0;}

转载于:https://www.cnblogs.com/l609929321/p/9519403.html

你可能感兴趣的文章