时间戳

首页 > 解决方案 > 数字的和和平方和-coprime

c++ - 数字的和和平方和-coprime

问题描述

对于段落 L、R，它的数字之和和它的平方和（十进制）是互质的。数一数L、R段落中有多少个数满足上述条件

当 R = 10^8 和 Max R = 10^18 时，我被困在 sub21 上超过时间限制：

#include<bits/stdc++.h>
using namespace std;
class tinhtong 
{ 
    public: 
    long long getSum(long long n) 
    {  
    long long int sum = 0; 
    while (n != 0) 
    { 
     sum = sum + (n % 10); 
     n = n/10; 
    }  
 return sum; 
    } 
};

class binhphuong 
{ 
    public: 
    long long getpow(long long n) 
    {  
    long long poww = 0; 
    while (n != 0) 
    { 
     poww = poww + (n % 10)*(n % 10); 
     n = n/10; 
    }  
 return poww; 
    } 
};

int main()
{
    tinhtong g;
    binhphuong h;
    long long TONG=0,k,l,ucln;
    long long int m,n;
    cin>>n>>m;
    for(n;n<=m;n++)
        {
            ucln=0;
            k=g.getSum(n);
            l=h.getpow(n);
            while(k!=0 && l!=0)
                {
                    if(k>l)
                    k-=l;
                else
                    l-=k;
                }
            if(k==0)
                ucln=l;
            else 
                ucln=k;
        if (ucln==1) 
            TONG++;
        }
    cout<<TONG;
    return 0;
}

标签： c++

解决方案

正如评论中提到的，您可以在一个循环中计算总和和平方和，避免多次调用相同的%操作。

此外，要计算两个数互质，最好使用欧几里德算法的版本，它使用模而不是减法。代码如下。

在这段代码中，我使用了平方和大于或等于和的事实。
我还使用了这样一个事实，即如果总和是 2 的倍数，那么平方和也是如此。

如果此代码不够快，您可以尝试评论中的建议，先将数字转换为字符串。

另一种可能性是在计算 GCD 之前检查两个数字是否是 3 或 5 的倍数，因为 GCD 计算可能更长。

#include <iostream>
#include <tuple>

std::pair<long long, long long> getSum_pow(long long n) {
    long long int sum = 0; 
    long long int sumP = 0; 
    while (n != 0) {
        long long r = n%10;
        sum += r; 
        sumP += r*r; 
        n = n/10; 
    }  
    return {sumP, sum}; 
};

int main() {

    long long TONG = 0, a, b;
    long long int m, n;
    std::cin >> n >> m;

    for(; n <= m; n++) {
        std::tie (a, b) = getSum_pow(n);
        if (b%2 == 0) continue;
        while (b != 0) {
            a = a%b;
            std::swap (a, b);
        }
        if (a == 1) {
            TONG++;
        }
    }

    std::cout << TONG;
    return 0;
}

推荐阅读